Information processing system and method of computation performed with an information processing system

• US 5,740,463 A
• Filed: 07/20/1995
• Issued: 04/14/1998
• Est. Priority Date: 07/22/1994
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Kondo, Akira, Onishi, Junji, Yamaguchi, Katsuhito, Nakashima, Shinji, Tsubota, Hirono, Tamura, Toshiyuki, Iwata, Makoto, Terada, Hiroaki, Oshima, Takeharu, Kotoh, Satoru, Komori, Shinji
• Primary Examiner(s): Pan, Daniel H.
• Application Number:
  US08/504,583
• Time in Patent Office: 999 Days
• Field of Search: 395/800, 395/200.15, 395/287, 395/210.16, 395/405, 395/200.1, 395/500, 395/200.02, 395/312, 395/773, 395/800.22, 395/11, 395/800.12, 395/124, 395/24 , 395/377, 395/21, 395/800.14, 395/200.78, 395/800.16, 395/800.11, 364/DIG. 1, 364/DIG. 2, 382/304, 382/306
• US Class Current: 712/11
• CPC Class Codes: G06F 15/803 Three-dimensional arrays or hypercubes
• CPC Class Codes: G06F 17/13 Differential equations using digital differential analysers G06F7/64

Abstract

Intercommunication of data between adjacent element processors (3) is performed through a memory unit (6) which is independently accessible to the respective element processors (3) without interfere with the operations of the other element processors (3). Thus, memory access and data transfer can be achieved without interfere with the operations of individual element processor (3). Furthermore, it becomes possible to solve differential equations by asynchronous communication system.

Claims

1. An information processing system, comprising:

plural buses and plural element processors which are networked by said plural buses, each of said plural element processors respectively including;

processing units for performing computing operations, and

data memories for storing data regarding said computing operations for performing computation by assigning, using at least one governing equation of a field which is described in at least one prescribed equation by using said plural element processors, plural lattice points obtained by spatially dividing said field to said plural element processors; and

plural data buses for providing mutual communications of said data between adjacent ones of said plural element processors,

wherein said computation is performed by operating said plural element processors asynchronously and independently by using said data transmitted through said plural data buses, and wherein each of said plural element processors directly writes to or reads from said data memories of adjacent element processors through one of said plural buses for communication therebetween.

4. The information processing system of either claim 1 or claim 2, further comprising transmission means for transmitting initial conditions and boundary conditions to said element processors.

5. The information processing system of either of claim 1 or claim 2, wherein

data communications between said adjacent element processors are performed individually for each of said element processors, asynchronously and repeatedly.

6. The information processing system of either claim 1 or claim 2, wherein

data communications between said adjacent element processors are message communications and performed with a multiple instruction stream and a multiple data stream.

7. The information processing system of either claim 1 or claim 2, wherein said data memories comprise accessible memories which are directly accessible to adjacent ones of said plural element processors.

8. The information processing system of claim 7, wherein said accessible memories are writable by said adjacent ones of said plural element processors.

9. The information processing system of claim 7, wherein said accessible memories comprise multiport memories.

10. The information processing system of either claim 1 or claim 2, wherein said data memories comprise first memories shared by adjacent ones of said plural element processors which are directly readable and writable from a plural number of said plural element processors which are connected to said first memories.

11. The information processing system of either claim 1 or claim 2, further comprising buffer means for temporarily buffering access demands to said data memories.

12. The information processing system of either claim 1 or claim 2, wherein said element processors further comprise:

buffer memories to which communicated data sent from adjacent ones of said plural element processors are written with an object name during communications between said adjacent ones of said plural element processors, and

searching for said communicated data with said object name at a specified timing from said buffer memories.

13. The information processing system of either claim 1 or claim 2, wherein said element processors respectively have matching memories for waiting for said data which is necessary for at least one of said computing operations, and

wherein at least one prescribed operation among said computing operations is performed in a corresponding one of said processing units at a point in a time sequence when said data which is necessary is available in a corresponding one of said matching memories.

14. The information processing system of either claim 1 or claim 2, wherein said element processors respectively further comprise program memories for rewriting a program controlling operations of said processing units.

15. The information processing system of claim 14, wherein said program memories comprise memories controlling processing of said lattice points by controlling the processing units to simultaneously execute a plural number of programs assigned to different areas of said program memories.

16. The information processing system of claim 15, further comprising a data flow system which includes a dynamic data driven system for simultaneously executing a single program on plural input data sets using identifiers.

17. The information processing system of either claim 1 or claim 2, wherein said processing units respectively comprise hardware circuits including arithmetic-logic elements which are wired in a shape based on a data flow graph according to a wired-logic for at least part of a data processing flow.

18. The information processing system of claim 17, wherein said processing units further respectively comprise arithmetic devices for directly executing operation codes for cumulatively adding 2N pieces of input data generated by respectively multiplying a first input by a second input, a third input by a fourth input, . . . , (2×

N-1)-th input by a (2×

N)-th input.

19. The information processing system of either claim 1 or claim 2, wherein

the processing units respectively comprise hardware circuits according to a single wired-logic, said hardware circuits loading in advance said data memories of said plural element processors with internal point bits indicating that said plural lattice points are positioned inside a computing area in said field or outside an object in said computing area with respect to all of said plural lattice points, with external point bits indicating that said plural lattice points are positioned outside said computing area or inside said object in said computing area, and with boundary condition bits indicating information of boundary conditions with respect to said plural lattice points positioned on a boundary of said computing area, and

said hardware circuits further comprise a controller to change a processing of a data flow graph according to said internal point bits, said external point bits and said boundary condition bits.

20. The information processing system of either claim 1 or claim 2, further comprising:

fine node couplings connecting adjacent ones of said plural element processors to each other, and

coarse node couplings connecting processors of said plural element processors to each other by skipping no less than one of said plural element processors therebetween.

21. The information processing system of either claim 1 or claim 2, wherein

said element processors respectively comprise output units for asynchronously reading output data, furnishing said output data with identifiers necessary for arranging sorting internal data, and sending said internal data to outside said plural element processors.

22. The information processing system of claim 21, further comprising an output data image processing unit for collecting said output data from said output units of said plural element processors and for generating visible images of said output data in real time based on said output data.

23. The information processing system of either claim 1 or claim 2, further comprising a coordinate conversion unit for converting a first coordinate system used by a host computer controlling said plural element processors to a second coordinate system used by said plural element processors when data are transferred from said host computer to said plural element processors, and for converting said second coordinate system used by said plural element processors to said first coordinate system used by said host computer when data are transferred from said plural element processors to said host computer.

24. The information processing system of either claim 1 or claim 2,

wherein said plural element processors are integrally controlled by a host computer and respectively comprise first convergence judging units, provided in each of said plural element processors and independently of said processing units, for judging convergence without disturbing computation by said processing units, and

wherein said information processing system further comprises:

first communication routes for dividing a plural number of said plural element processors into plural groups and for connecting said first convergence judging units of respective ones of said plural element processors into a unidirectional closed looped or into a centralized form in said plural groups;

second convergence judging units, connected to said first communication routes respectively, for integrating judgement results of convergence of all said first convergence judging units in said plural groups; and

second communication routes for connecting all of the second convergence judging units of said plural groups in the unidirection closed loop or in the centralized form.

25. The information processing system of either claim 1 or claim 2, wherein said plural element processors each comprise at least one processing means,

said system further comprising:

at least one route for transferring messages of a plurality of said plural element processors;

first convergence judging means for judging convergences on said plural element processors;

first message sending means for sending a first message indicating convergence on a prescribed element processor of said plural element processors when said first convergence judging means judges the convergence on said prescribed element processor or a respective processing means of said prescribed element processor;

second message sending means for sending a second message indicating the convergence on one of the plural element processor or the processing means based on receiving said first or second message from an adjacent element processor or an adjacent processing means after said adjacent element processor or said adjacent processing means received said first or second message; and

second convergence judging means for judging the convergence of all said plural element processors by transferring said second message one after another through said at least one route by said second sending means.

26. The information processing system of claim 25, wherein

said at least one route includes a plurality of different routes connecting said processing means, and

said second convergence judging means confirms said convergence of all said plural element processors in a multiplex fashion by the messages transferred one after another through said plurality of different routes.

27. The information processing system of either claim 1 or claim 2, wherein said plural element processors share said data memories between adjacent element processors, and each of said plural element processors comprises an input/output control unit commonly connected to a subset of said plural data memories shared with said adjacent element processors for controlling input/output of data with one of said subset of said plural data memories by switching a direction of communication according to a demand for access.

28. The information processing system of either claim 1 or claim 2, further comprising

plural registers provided in correspondence to said plural element processors for temporarily storing results of a judgement of a convergence of an operation executed by each of said plural element processors;

and

a wired OR circuit for generating a logical product of an output of said plural registers.

2. An information processing system, comprising:

plural buses and plural element processors which are networked by said plural buses, each of said plural element processors respectively including;

processing units for performing computing operations, and

data memories for storing data regarding said computing operations for performing computation by assigning, using at least one governing equation of a field which is described in at least one prescribed equation by using said plural element processors, plural lattice points obtained by spatially dividing said field and plural time steps corresponding to identical ones of said lattice points to said plural element processors; and

plural data buses for providing mutual communications of said data between adjacent ones of said plural element processors,

wherein said computation is performed by operating said plural element processors asynchronously and independently by using said data transmitted through said plural data buses, and wherein each of said plural element processors directly writes to or reads from said data memories of adjacent element processors through one of said plural buses for communication therebetween.

3. The information processing system of claim 2, wherein said plural element processors comprise a pipeline of element processors in a direction of a time base, and form a plural number of two-dimensional planes arranged along the time base.

29. An information processing method for use with plural element processors respectively including:

processing units for performing computing operations, and data memories for storing data regarding said computing operations, the method comprising the steps of;

spatially dividing a field which is described in at least one prescribed equation by using at least one governing equation,

assigning plural lattice points obtained by spatially dividing to said plural element processors, and

communicating adjacent ones of said plural element processors using plural data buses with said plural element processors directly writing to or reading from data memories of said adjacent ones,

operating said plural element processors asynchronously and independently by using said data transmitted through said plural data buses.

32. The information processing method of either claim 29 or claim 30, wherein

said at least one prescribed equation includes at least one differential equation, and

said at least one prescribed equation obtains the solution to said at least one differential equation by operating said element processors asynchronously and independently by finite difference method.

33. The information processing method of claim 32, wherein said at least one prescribed differential equation includes at least one partial differential equation or at least one ordinary differential equation.

34. The information processing method of either claim 29 or claim 30, wherein

said element processors take charge of computation of a plural number of lattice points obtained by spatially dividing said field respectively, and

the number corresponding to said lattice points or the base address of the data area corresponding to said lattice points on said data memories are used as input tokens to control said computation performed by said element processors.

35. The information processing method of either claim 29 or claim 30, further comprising the step of transmitting initial conditions and boundary conditions to said plural element processors.

36. The information processing method of claim 35, wherein said data memories comprise multiport memories.

37. The information processing method of either claim 29 or claim 30, wherein the step of communicating comprises asynchronously and repeatedly communicating said data between adjacent processors of said plural element processors individually for each of said plural element processors.

38. The information processing method of either claim 29 or claim 30, wherein the step of communicating comprises communicating said data using a multiple instruction stream and a multiple data stream.

39. The information processing method of either claim 29 or claim 30, wherein said data memories comprise first memories shared by adjacent ones of said plural element processors which are directly readable and writable from a plural number of said plural element processors which are connected to said first memories.

40. The information processing method of either claim 29 or claim 30, further comprising the step of temporarily buffering access demands to said data memories by buffer means.

41. A information processing method as claimed in either claim 29 or 30 further comprising the steps of:

sending communicated data to buffer memories of adjacent ones of said element processors, said communicated data including an object name; and

searching for said communicated data in said buffer memories using said object name at a specific timing.

42. The information processing method of either claim 29 or 30, further comprising the step of waiting for said data which is necessary for at least one of said computing operations to be written to matching memories, and

performing at least one prescribed operation among said computing operations in a corresponding one of said processing units at a point in a time sequence when said data which is necessary is available in a corresponding one of said matching memories.

43. The information processing method of either claim 29 or claim 30, further comprising the step of controlling said processing units using a program written into program memories of said element processors.

44. The information processing method of either claim 29 or claim 30, further comprising the steps of:

loading in advance said data memories of said plural element processors with internal point bits indicating that said plural lattice points are positioned inside a computing area in said field or outside an object in said computing area with respect to all of said plural lattice points, with external point bits indicating that said plural lattice points are positioned outside said computing area or inside said object in said computing area, and with boundary condition bits indicating information of boundary conditions with respect to said plural lattice points positioned on a boundary of said computing area, and

changing a processing of a data flow graph according to said internal point bits, said external point bits and said boundary condition bits.

45. The information processing method of either claim 29 or claim 30, wherein the step of controlling comprises controlling processing of said lattice points by controlling said processing units to simultaneously execute a plural number of programs assigned to different areas of said program memories.

46. The information processing method of claim 45, further comprising the step of simultaneously executing a single program on plural input data sets using identifiers according to a data flow system which includes a dynamic data driven system.

47. The information processing method of claim 46, wherein

said processing units calculate the address of said data memories which store data regarding said adjacent element processors and make reference to and renewal of said data memories by using the address of said data memories, based on the value of said identifiers assigned to said input data.

48. The information processing method of either claim 29 or claim 30, wherein

said processing units respectively have hardware circuits in which arithmetic-logic elements are wired in the shape based on a data flow graph according to the wired-logic for part or whole of the data processing flow.

49. The information processing method of claim 29, wherein the step of communicating comprises:

leveling a number of times each of said lattice points communicates by performing dummy communications even for lattice points of said lattice points with small number of communications when solving said at least one governing equation of said field so that said lattice points on border areas communicate equally.

50. The information processing method of either claim 29 or claim 30, wherein

said processing units respectively have hardware circuits according to one same wired-logic,

said hardware circuits load in advance said data memories of said element processors with internal point bits indicating that said plural lattice points are positioned inside a computing area in said field or outside an object in said computing area with respect to all of said plural lattice points, with said external point bits indicating that said plural lattice points are positioned outside said computing area or inside said object in said computing area, and

said hardware circuits change the processing of the data flow graph according to said internal point bits, said external point bits and said boundary condition bits.

51. The information processing method of either claim 29 or claim 30, further comprising the steps of:

multiplying a first input by a second input, a third input by a fourth input, . . . , and (2×

N-1)-th input; and

by a (2×

N)-th input; and

cumulatively adding 2N pieces of input data generated by said multiplying step.

52. The information processing method of either claim 29 or claim 30, wherein the step of computing comprises

leveling the number of operations at all of said lattice points are performed by performing dummy operations even for said lattice points on border areas.

53. The information processing method of either claim 29 or claim 30, wherein the step of computing comprises computing finite differences at

each of said lattice points to find a solution to a differential equation;

and wherein the step of communicating comprises communicating between adjacent lattice points of said plural lattice points, information indicating the necessity or not of communication and a method of communication for each of said plural lattice points.

54. The information processing method of either claim 29 or claim 30, wherein the step of computing finite differences comprises assigning a memory area to each of said plural lattice points, and wherein said step of communicating between adjacent lattice points comprises providing each of said lattice points with information for indicating said memory area to be used for communication in each direction when communicating.

55. The information processing method of claim 54, further comprising the step of indicating a common dummy area in each direction where communication is impossible.

56. The information processing method of claim 54, wherein the step of assigning comprises

assigning a virtual data area simulating lattice points which are closest to a border of a computation area and found outside said computation area.

57. The information processing method of either claim 29 or claim 30, wherein the step of communicating comprises:

transmitting, between adjacent element processors, change in data value between iterations, only if said change is no larger than a prescribed value.

58. The information processing method of either claim 29 or claim 30, further comprising the steps of:

coupling together adjacent ones of said plural element processors using fine node couplings; and

coupling together, using coarse node couplings, said plural element processors by skipping no less than one of said plural element processors therebetween.

59. The information processing method of claim 58, wherein

wherein said step of computing comprises computing said at least one prescribed equation by alternately performing 1) computation by said plural element processors connected by said coarse node coupling and 2) computation by said plural element processors connected by said free node coupling.

60. The information processing method of either claim 29 or claim 30, wherein the step of computing comprises partially calculating

said at least one governing equation of said field using only part of said plural lattice points selected, and completely calculating in parallel said at least one governing equation of said field using all of said plural lattice points.

61. The information processing method of claim 60, wherein the steps of partially and completely calculating utilize different algorithms.

62. The information processing method of claim 61, further comprising the step of stopping calculation if an amount of change between iterations is no larger than a prescribed amount.

63. The information processing method of claim 62, wherein the step of stopping comprises reducing the amount of change required for stopping based on a rate of convergence.

64. The information processing method of either claim 29 or claim 30, comprising the steps of:

asynchronously reading output data using said element processors,

furnishing said output data with identifiers necessary for arranging sorting internal data, and

sending said internal data to outside said plural element processors.

65. The information processing method of claim 64, further comprising the steps of collecting said output data from said plural element processors, and generating visible images of said output data in real time based on said output data.

66. The information processing method of either claim 29 or claim 30, further comprising the steps of converting a first coordinate system used by a host computer controlling said plural element processors to a second coordinate system used by said plural element processors when data are transferred from said host computer to said plural element processors, and

converting said second coordinate system used by said plural element processors to said first coordinate system used by said host computer when data are transferred from said plural element processors to said host computer.

67. The information processing method of either claim 29 or claim 30, further comprising the steps of:

integrally controlling said plural element processors using a host computer,

judging convergence without disturbing computation by the processing units, and

dividing a plural number of said plural element processors into plural groups; and

connecting said convergence judging units of respective ones of said plural element processors into a unidirectional closed looped or into a centralized form in said plural groups; and

integrating judgement results of convergence of all said first convergence judging units in said plural groups.

68. The information processing method of either claim 29 or claim 30, wherein

the step of computing further comprises the steps of:

(a) judging convergences on each of said plural element processors or no less than one processing means assigned to each of said plural element processors;

(b) sending a first message indicating a prescribed element processor or a processing means of said prescribed element, when said information processing system judges the convergence on said prescribed element processor or said processing means of said prescribed element;

(c) sending a second message indicating the convergence on the element processor or the processing means receiving said first or second message from an adjacent element processor or an adjacent processing means after said adjacent element processor or said adjacent processing means receives said first or second message; and

(d) judging the convergence of all said plural element processors by transferring said second message one after another by repeating said step (c).

69. The information processing method of claim 68, further comprising the step of repeating said step (a) to step (d) for a plurality of confirmations of said convergence of all said plural element processors.

70. The information processing method of claim 69, further comprising the step of confirming said convergence of all said element processors in a multiplex fashion by receiving the messages transferred one after another through a plurality of different routes.

71. The information processing method of claim 70, wherein the step d) of judging comprises the steps of:

determining general convergence; and

stopping processing of all said plural element processors or said processing means after determining general convergence.

72. The information processing method of either claim 29 or 30, further comprising steps of:

initializing a storing means for storing the results of judgement of convergence; and

judging convergence or not of the computation of said lattice points of said plural element processors,

judging if convergence has not yet been reached, and

setting said storing means to a prescribed logical value if said judging step determines that said convergence has not yet been reached.

73. The information processing method of either claim 29 or claim 30, further comprising the steps of:

sharing said data memories between a number of adjacent element processors,

controlling input/output of data with one of the plural data memories by switching a direction of communication according to a demand for access, and

accessing, using said plural element processors, a contents of said data memories.

74. The information processing method of either claim 29 or claim 30, further comprising the steps of:

temporarily storing, in plural registers provided in correspondence to said plural element processors, results of judgement of a convergence of corresponding element processors, and taking a logical product of said results of judgement stored in said plural registers with the wired OR circuit, while executing operations.

75. The method of computation performed by using an information processing system of either claim 29 or claim 30, wherein

the number of lattice points per one element processor including lattice points for analysis in which lattice factors exist is smaller than the number of lattice points per one element processor not including any unstable points for analysis.

76. The information processing method of either claim 29 or claim 30, further comprising the steps of:

judging convergences on said plural element processors or on a corresponding processing means assigned to each of said plural element processors;

sending a first message indicating the convergence on a prescribed element processor based on said judging step;

sending a second message indicating the convergence on the element processor or the processing means receiving said first or second message from an adjacent element processor or an adjacent processing means after said adjacent element processor or said adjacent processing means receives said first or second message; and

judging the convergence of all said plural element processors by transferring said second message one after another through said at least one route by said second sending means.

77. The information processing method of claim 76, wherein the step of judging the convergence of all said plural element processors comprises determining convergence of all said plural element processors in a multiplex fashion using the messages transferred one after another through said plurality of different routes.

30. An information processing method for use with plural element processors respectively including:

processing units for performing computing operations, and data memories for storing data regarding said computing operations, the method comprising the steps of;

spatially dividing a field and plural time steps which are described in at least one prescribed equation by using at least one governing equation,

assigning plural lattice points obtained by spatially dividing to said plural element processors, and

communicating adjacent ones of said plural element processors using plural data buses with said plural element processors directly writing to or reading from data memories of said adjacent ones.

31. The information processing method of claim 30, further comprising the step of pipelining said plural element processors into a pipeline of element processors in a direction of a time base, and

forming a plural number of two-dimensional planes arranged along the time base to be constructed three-dimensionally, when a two-dimensional analytical solution is looked for.