초록 ▼

An approach to performing graph-based computation uses one or both of an efficient startup approach and efficient control using process pools. Efficient startup of a graph-based computation involves precomputing data representing a runtime structure of a computation graph such that an instance of th

An approach to performing graph-based computation uses one or both of an efficient startup approach and efficient control using process pools. Efficient startup of a graph-based computation involves precomputing data representing a runtime structure of a computation graph such that an instance of the computation graph is formed using the precomputed data for the required type of graph to form the runtime data structure for the instance of the computation graph. Pools of processes that are each suitable for performing computations associated with one or more vertices of the computation graphs are formed such that at runtime, members of these pools of processes are dynamically assigned to particular vertices of instances of computation graphs when inputs are available for processing at those vertices.

대표청구항 ▼

What is claimed is: 1. A method for executing, on a computer system, graphs-expressing computations including: providing, on the computer system, two or more graph templates each associated with a different type of computation graph, each computation graph including a number of graph elements each

What is claimed is: 1. A method for executing, on a computer system, graphs-expressing computations including: providing, on the computer system, two or more graph templates each associated with a different type of computation graph, each computation graph including a number of graph elements each associated with a corresponding computation; managing one or more pools of computing resources, wherein each graph element of a computation is associated with a corresponding one of the pools of computing resources; and receiving one or more data streams, each associated with a corresponding graph template, processing the data streams, including for each of the data streams, identifying the graph template associated with the data stream, forming a graph instance from identified graph template, for each graph element of the graph instance, assigning computing resources from corresponding pools of computing resources, and processing the data stream with the graph instance, including performing the computations corresponding to the graph elements of such graph instance using the assigned computing resources. 2. The method of claim 1, wherein the graph elements include vertices of the computation graph. 3. The method of claim 1, wherein the graph elements include links of the computation graph. 4. The method of claim 1, wherein the computation resources include processes. 5. The method of claim 1, wherein the computation resources include processes threads. 6. The method of claim 1, wherein the computation resources include database connections. 7. The method of claim 1, wherein providing the two or more graph templates includes storing the templates in volatile memory. 8. The method of claim 1, wherein providing the two or more graph templates includes storing the templates in non-volatile memory. 9. The method of claim 1, wherein forming the graph instance from the graph template includes forming such instance in volatile memory. 10. The method of claim 9, wherein forming the graph instance includes allocating a portion of the memory to the graph instance and copying the graph template to such portion of the memory. 11. The method of claim 1, wherein assigning computing resources includes assigning each of such resources dynamically for part of the computation on the data stream. 12. The method of claim 11, wherein assigning each of the resources dynamically for processing part of the computation occurs when at least some part of all of the inputs for such part of the computation are available. 13. The method of claim 12, wherein assigning each of the resources dynamically for processing part of the computation occurs when all of the inputs for such part of the computation are available. 14. The method of claim 11, wherein assigning each of the resources dynamically includes deassigning the computation resource from the graph element. 15. The method of claim 1, wherein assigning computing resources includes assigning each of such computing resources for the graph element for processing all of the data stream. 16. The method of claim 1, further including releasing the computing resources assigned to graph elements and destroying the instance of the graph. 17. The method of claim 1, wherein processing the one or more data streams includes concurrently processing at least two data streams each associated with a different computation graph. 18. The method of claim 17, wherein at least one graph element of instances of each of the different computation graphs is associated with a same corresponding pool of computation resources. 19. The method of claim 18, wherein at least one computing resource of the same corresponding pool of computation resources is assigned at different times to the at least one graph element of the instances of the different computation graphs. 20. The method of claim 1, wherein managing one or more pools of computing resources includes forming at least two pools of computing resources, wherein a first graph element of a computation is associated with a corresponding first pool of computing resources and a second graph element of a computation is associated with a corresponding second pool of computing resources. 21. The method of claim 1, wherein providing the two or more graph templates including storing the temples in an external storage. 22. The method of claim 21, wherein forming the graph instance from the graph template includes forming said instance in a working storage. 23. The method of claim 1, wherein forming the graph instance from the graph template includes forming said instance in temporary memory. 24. A computer program, stored on a computer-readable medium, for executing on a computer system, graphs expressing computations, the computer program comprising instructions for causing a computer system to: provide two or more graph templates each associated with a different type of computation computation graph, each computation graph including a number of graph elements each associated with a corresponding computation; manage one or more pools of computing resources, wherein each graph element of a computation is associated with a corresponding one of the pools of computing resources; and process one or more data streams, each associated with a corresponding graph template, including for each of the data streams: identifying the graph template associated with the data stream, forming a graph instance from the identified graph template, for each graph elements of the graph instance, assigning computing resources from corresponding pools, and processing the data stream with the graph instance, including performing the computation corresponding to the graph elements of such graph instance using the assigned computing resources. 25. The computer program of claim 24, wherein managing one or more pools of computing resources includes forming at least two pools of computing resources, wherein a first graph element of computation is associated with a corresponding first pool of computing resources and a second graph element of a computation is associated with a corresponding second pool of computing resources. 26. The computer program of claim 24, wherein the graph elements include vertices of the computation graph. 27. The computer program of claim 24, wherein the graph elements include links of the computation graph. 28. The computer program of claim 24, wherein the computing resources include processes. 29. The computer program of claim 24, wherein the computing resources include processes threads. 30. The computer program of claim 24, wherein the computing resources include database connections. 31. The computer program of claim 24, wherein providing the two or more graph templates include storing the templates in volatile memory. 32. The computer program of claim 24, wherein providing the two or more graph templates includes storing the templates in non-volatile memory. 33. The computer program of claim 24, wherein forming the graph instance from the graph template includes forming such instance in volatile memory. 34. The computer program of claim 33, wherein forming the graph instance includes allocating a portion of the memory to the graph instance and copying the graph template to such portion of the memory. 35. The computer program of claim 24, wherein assigning computing resources includes assigning each of such resources dynamically for part of the computation on the data stream. 36. The computer program of claim 35, wherein assigning each of the resources dynamically for processing part of the computation occurs when at least some part of all of the inputs for such part of the computation are available. 37. The computer program of claim 36, wherein assigning each of the resources dynamically for processing part of the computation occurs when all of the inputs for such part of the computation are available. 38. The computer program of claim 35, wherein assigning each of the resources dynamically includes deassigning the computing resource from the graph element. 39. The computer program of claim 24, wherein assigning computing resources includes assigning each of such computing resources for the graph element for processing all of the data stream. 40. The computer program of claim 24, wherein processing the one or more data streams further includes releasing the computing resources assigned to graph elements and destroying the instance of the graph. 41. The computer program of claim 24, wherein processing the one or more data streams includes concurrently processing at least two data streams each associated with a different computation graph. 42. The computer program of claim 41, wherein at least one graph element of instances of each of the different computation graphs is associated with a same corresponding pool of computing resources. 43. The computer program of claim 42, wherein at least one computing resource of the same corresponding pool of computing resources is assigned at different times to the at least one graph element of the instances of the different computation graphs. 44. The computer program of claim 24, wherein providing the two or more graph templates includes storing the templates in an external storage. 45. The computer program of claim 44, wherein forming the graph instance from the graph template includes forming said instance in a working storage. 46. The computer program of claim 24, wherein forming the graph instance from the graph template includes forming said instance in temporary memory. 47. A method for processing data, on a computer system, including: providing, on the computer system, two or more graph templates each associated with a different set of operations to be performed on an incoming data stream and each representing a computation graph including a number of graph elements each associated with a corresponding computation; managing one or more pools of computing resources, wherein each graph element of a computation is associated with a corresponding one of the pools of computing resources; receiving one or more data streams; and for each of the data streams, identifying the graph template associated with the data stream, forming a graph instance from the identified graph template, for each graph element of the graph instance, assigning computing resources from a corresponding pool of computing resources, using the data stream as input to the graph instance, and performing the computations corresponding to the graph elements of such graph instance using the assigned computing resources. 48. The method of claim 47, wherein the graph elements include vertices of the computation graph. 49. The method of claim 47, wherein the graph elements include links of the computation graph. 50. The method of claim 47, wherein the computing resources include processes. 51. The method of claim 47, wherein the computing resources include process threads. 52. The method of claim 47, wherein the computing resources include database connections. 53. The method of claim 47, wherein providing the two or more graph templates includes storing the templates in volatile memory. 54. The method of claim 47, wherein providing the two or more graph templates includes storing the templates in non-volatile memory. 55. The method of claim 47, wherein forming the graph instance from the graph template includes forming such instance in volatile memory. 56. The method of claim 55, wherein forming the graph instance includes allocating a portion of the memory to the graph instance and copying the graph template to such portion of the memory. 57. The method of claim 47, wherein assigning computing resources includes assigning each of such resources dynamically for part of the computation on the data stream. 58. The method of claim 57, wherein assigning each of the resources dynamically for processing part of the computation occurs when at least some part of all of the inputs for such part of the computation are available. 59. The method of claim 58, wherein assigning each of the resources dynamically for processing part of the computation occurs when all of the inputs for such part of the computation are available. 60. The method of claim 57, wherein assigning each of the resources dynamically includes deassigning the computing resource from the graph element. 61. The method of claim 47, wherein assigning computing resources includes assigning each of such computing resources for the graph element for processing all of the data stream. 62. The method of claim 47, further including, for each of the data streams, releasing the computing resources assigned to graph elements and destroying the instance of the graph. 63. The method of claim 47, further including concurrently processing at least two data streams each associated with a different computation graph. 64. The method of claim 63, wherein at least one graph element of instances of each of the different computation graphs is associated with a same corresponding pool of computing resources. 65. The method of claim 64, wherein at least one computing resource of the same corresponding pool of computing resources is assigned at different times to the at least one graph element of the instances of the different computation graphs. 66. The method of claim 47, wherein managing one or more pools of computing resources includes forming at least two pools of computing resources, wherein a first graph element of a computation is associated with a corresponding first pool of computing resources and a second graph element of a computation is associated with a corresponding second pool of computing resources. 67. The method of claim 47, wherein providing the two or more graph templates includes storing the templates in an external storage. 68. The method of claim 67, wherein forming the graph instance from the graph template includes forming said instance in a working storage. 69. The method of claim 47, wherein forming the graph instance from the graph template includes forming said instance in temporary memory. 70. A computer program, stored on a computer-readable medium, for processing data, the computer program comprising instructions for causing a computer system to: provide two or more graph templates each associated with a different set of operations to be performed on an incoming data stream and each representing a computation graph including a number of graph elements each associated with a corresponding computation; manage one or more pools of computing resources, wherein each graph element of a computation is associated with a corresponding one of the pools of computing resources; receive one or more data streams; and for each of the data streams, identify the graph template associated with the data stream, form a graph instance from the identified graph template, for each graph element of the graph instance, assign computing resources from a corresponding pool of computing resources, use the data stream as input to the graph instance, and perform the computations corresponding to the graph elements of such graph instance using the assigned computing resources. 71. The computer program of claim 70, wherein the graph elements include vertices of the computation graph. 72. The computer program of claim 70, wherein the graph elements include links of the computation graph. 73. The computer program of claim 70, wherein the computing resources include processes. 74. The computer program of claim 70, wherein the computing resources include process threads. 75. The computer program of claim 70, wherein the computing resources include database connections. 76. The computer program of claim 70, wherein providing the two or more graph templates includes storing the templates in volatile memory. 77. The computer program of claim 70, wherein providing the two or more graph templates includes storing the templates in non-volatile memory. 78. The computer program of claim 70, wherein forming the graph instance from the graph template includes forming such instance in volatile memory. 79. The computer program of claim 78, wherein forming the graph instance includes allocating a portion of the memory to the graph instance and copying the graph template to such portion of the memory. 80. The computer program of claim 70, wherein assigning computing resources includes assigning each of such resources dynamically for part of the computation on the data stream. 81. The computer program of claim 80, wherein assigning each of the resources dynamically for processing part of the computation occurs when at least some part of all of the inputs for such part of the computation are available. 82. The computer program of claim 81, wherein assigning each of the resources dynamically for processing part of the computation occurs when all of the inputs for such part of the computation are available. 83. The computer program of claim 80, wherein assigning each of the resources dynamically includes deassigning the computing resource from the graph element. 84. The computer program of claim 80, wherein assigning computing resources includes assigning each of such computing resources for the graph element for processing all of the data stream. 85. The computer program of claim 80, further including, for each of the data streams, releasing the computing resources assigned to graph elements and destroying the instance of the graph. 86. The computer program of claim 80, further including concurrently processing at least two data streams each associated with a different computation graph. 87. The computer program of claim 86, wherein at least one graph element of instances of each of the different computation graphs is associated with a same corresponding pool of computing resources. 88. The computer program of claim 87, wherein at least one computing resource of the same corresponding pool of computing resources is assigned at different times to the at least one graph element of the instances of the different computation graphs. 89. The computer program of claim 70, wherein managing one or more pools of computing resources includes forming at least two pools of computing resources, wherein a first graph element of a computation is associated with a corresponding first pool of computing resources and a second graph element of a computation is associated with a corresponding second pool of computing resources. 90. The computer program of claim 70, wherein providing the two or more graph templates includes storing the templates in an external storage. 91. The computer program of claim 90, wherein forming the graph instance from the graph template includes forming said instance in a working storage. 92. The computer program of claim 70, wherein forming the graph instance from the graph template includes forming said instance in temporary memory. 93. A system for processing data, including: two or more graph templates stored in data storage, each associated with a different set of operations to be performed on an incoming data stream and each representing a computation graph including a number of graph elements each associated with a corresponding computation; means for managing one or more pools of computing resources, wherein each graph element of a computation is associated with a corresponding one of the pools of computing resources; means for receiving one or more data streams; and means for processing the data streams, including for each of the data streams, identifying the graph template associated with the data stream, forming a graph instance from the identified graph template, for each graph element of the graph instance, assigning computing resources from a corresponding pool of computing resources, using the data stream as input to the graph instance, and performing the computations corresponding to the graph elements of such graph instance using the assigned computing resources. 94. The system of claim 93, wherein the graph elements include vertices of the computation graph. 95. The system of claim 93, wherein the graph elements include links of the computation graph. 96. The system of claim 93, wherein the computing resources include processes. 97. The system of claim 93, wherein the computing resources include process threads. 98. The system of claim 93, wherein the computing resources include database connections. 99. The system of claim 93, wherein providing the two or more graph templates includes storing the templates in volatile memory. 100. The system of claim 93, wherein providing the two or more graph templates includes storing the templates in non-volatile memory. 101. The system of claim 93, wherein forming the graph instance from the graph template includes forming such instance in volatile memory. 102. The system of claim 101, wherein forming the graph instance includes allocating a portion of the memory to the graph instance and copying the graph template to such portion of the memory. 103. The system of claim 93, wherein assigning computing resources includes assigning each of such resources dynamically for part of the computation on the data stream. 104. The system of claim 103, wherein assigning each of the resources dynamically for processing part of the computation occurs when at least some part of all of the inputs for such part of the computation are available. 105. The system of claim 103, wherein assigning each of the resources dynamically for processing part of the computation occurs when all of the inputs for such part of the computation are available. 106. The system of claim 103, wherein assigning each of the resources dynamically includes deassigning the computing resource from the graph element. 107. The system of claim 93, wherein assigning computing resources includes assigning each of such computing resources for the graph element for processing all of the data stream. 108. The system of claim 93, further including, for each of the data streams, releasing the computing resources assigned to graph elements and destroying the instance of the graph. 109. The system of claim 93, further including concurrently processing at least two data streams each associated with a different computation graph. 110. The system of claim 109, wherein at least one graph element of instances of each of the different computation graphs is associated with a same corresponding pool of computing resources. 111. The system of claim 110, wherein at least one computing resource of the same corresponding pool of computing resources is assigned at different times to the at least one graph element of the instances of the different computation graphs. 112. The system of claim 93, wherein managing one or more pools of computing resources includes forming at least two pools of computing resources, wherein a first graph element of a computation is associated with a corresponding first pool of computing resources and a second graph element of a computation is associated with a corresponding second pool of computing resources. 113. The system of claim 93, wherein providing the two or more graph templates includes storing the templates in an external storage. 114. The system of claim 113, wherein forming the graph instance from the graph template includes forming said instance in a working storage. 115. The system of claim 93, wherein forming the graph instance from the graph template includes forming said instance in temporary memory. 116. A system for executing, on a computer system, graphs expressing computations including: two or more graph templates stored in data storage each associated with a different type of graph-based computation, each template comprising a number of graph elements each associated with a corresponding computation; means for managing one or more pools of computing resources, wherein each graph element of graph template is associated with a corresponding one of the pools of computing resources; and means for processing one or more data streams, each associated with a corresponding graph template, including for each of the data streams, identifying the graph template associated with the data stream, forming a graph instance from the identified graph template, said graph instance having a graph elements corresponding to the graph elements of the graph template, for each graph element of the graph instance, assigning computing resources from a corresponding one of the pools of computing resources, and processing the data stream with the graph instance, including performing computations corresponding to the graph elements of such graph instance using the assigned computing resources. 117. The system of claim 116, wherein the graph elements include vertices of the computation graph. 118. The system of claim 116, wherein the graph elements include links of the computation graph. 119. The system of claim 116, wherein the computing resources include processes. 120. The system of claim 116, wherein the computing resources include process threads. 121. The system of claim 116, wherein the computing resources include database connections. 122. The system of claim 116, wherein providing the two or more graph templates includes storing the templates in volatile memory. 123. The system of claim 116, wherein providing the two or more graph templates includes storing the templates in non-volatile memory. 124. The system of claim 116, wherein forming the graph instance from the graph template includes forming such instance in volatile memory. 125. The system of claim 124, wherein forming the graph instance includes allocating a portion of the memory to the graph instance and copying the graph template to such portion of the memory. 126. The system of claim 116, wherein assigning computing resources includes assigning each of such resources dynamically for part of the computation on the data stream. 127. The system of claim 126, wherein assigning each of the resources dynamically for processing part of the computation occurs when at least some part of all of the inputs for such part of the computation are available. 128. The system of claim 127, wherein assigning each of the resources dynamically for processing part of the computation occurs when all of the inputs for such part of the computation are available. 129. The system of claim 126, wherein assigning each of the resources dynamically includes deassigning the computing resource from the graph element. 130. The system of claim 116, wherein assigning computing resources includes assigning each of such computing resources for the graph element for processing all of the data stream. 131. The system of claim 116, wherein processing the one or more data streams further includes releasing the computing resources assigned to graph elements and destroying the instance of the graph. 132. The system of claim 116, wherein processing the one or more data streams includes concurrently processing at least two data streams each associated with a different computation graph. 133. The system of claim 132, wherein at least one graph element of instances of each of the different computation graphs is associated with a same corresponding pool of computing resources. 134. The system of claim 133, wherein at least one computing resource of the same corresponding pool of computing resources is assigned at different times to the at least one graph element of the instances of the different computation graphs. 135. The system of claim 116, wherein managing one or more pools of computing resources includes forming at least two pools of computing resources, wherein a first graph element of a computation is associated with a corresponding first pool of computing resources and a second graph element of a computation is associated with a corresponding second pool of computing resources. 136. The system of claim 116, wherein providing the two or more graph templates includes storing the templates in an external storage. 137. The system of claim 136, wherein forming the graph instance from the graph template includes forming said instance in a working storage. 138. The system of claim 116, wherein forming the graph instance from the graph template includes forming said instance in temporary memory.