Heterogeneous computations on homogeneous input data

• US 10,491,663 B1
• Filed: 10/28/2013
• Issued: 11/26/2019
• Est. Priority Date: 10/28/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: White, Taylor James, Johnson, Albert Cooper
• Primary Examiner(s): Bates, Kevin T
• Assistant Examiner(s): Scott, Mark A
• Application Number:
  US14/065,102
• Time in Patent Office: 2,220 Days
• Field of Search: 709201
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

Methods and systems for performing heterogeneous computations on homogeneous input data are disclosed. A plurality of computational specifications are distributed among a plurality of worker nodes. The computational specifications comprise definitions of a plurality of heterogeneous computations. The heterogeneous computations are performed using the worker nodes. Individual ones of the heterogeneous computations are performed based on the set of input data and corresponding ones of the computational specifications, and individual ones of the heterogeneous computations produce respective results. An aggregate result is generated based on the respective results of the heterogeneous computations.

Claims

1. A system, comprising:

a plurality of computing devices configured to implement a heterogeneous computation system comprising one or more master nodes, a plurality of worker nodes, and one or more aggregator nodes, wherein the one or more master nodes are configured to;

send information indicative of a plurality of computational specifications to the plurality of worker nodes, wherein the plurality of computational specifications comprise definitions of a plurality of heterogeneous computations;

wherein, for a set of input data, each worker node of the plurality of worker nodes is configured to;

load the set of input data; and

perform one or more of the plurality of heterogeneous computations based on the plurality of computational specifications and the set of input data, wherein different ones of the worker nodes perform different respective computational specifications to solve a same problem using the same set of input data to produce respective results, and wherein the respective computational specifications to solve the same problem comprise;

same respective algorithms configured to be concurrently implemented using the same set of input data by different types of computing platforms or different types of processors of the different ones of the worker nodes; and

wherein the one or more aggregator nodes are configured to;

generate an aggregate result based at least on the respective results produced using the same set of input data.

2. The system as recited in claim 1, wherein the plurality of computational specifications comprise one or more sets of executable instructions, one or more sets of interpretable instructions, or one or more service requests.

3. The system as recited in claim 1, wherein the plurality of worker nodes comprise a plurality of specification interpreters, wherein the specification interpreters are configured to interpret or execute the computational specifications to produce the respective results based on the set of input data.

4. A computer-implemented method, comprising:

distributing a plurality of computational specifications among a plurality of worker nodes, wherein the plurality of computational specifications comprise descriptions of a plurality of heterogeneous computations;

performing the plurality of heterogeneous computations using the plurality of worker nodes, wherein individual ones of the plurality of heterogeneous computations are performed based on a set of input data and corresponding ones of the plurality of computational specifications, and wherein different ones of the worker nodes perform different respective computational specifications to solve a same problem using the same set of input data to produce respective results, and wherein the respective computational specifications to solve the same problem comprise;

same respective algorithms configured to be concurrently implemented using the same set of input data by different types of computing platforms or different types of processors of the different ones of the worker nodes; and

generating an aggregate result based at least on the respective results produced using the same set of input data.

5. The method as recited in claim 4, wherein the plurality of computational specifications comprise one or more sets of executable instructions, one or more sets of interpretable instructions, or one or more service requests.

6. The method as recited in claim 4, wherein performing the plurality of heterogeneous computations using the plurality of worker nodes comprises using a plurality of specification interpreters to interpret or execute the computational specifications to produce the respective results based on the set of input data.

7. The method as recited in claim 4, wherein each of at least two of the respective results is produced by a corresponding worker node of the plurality of worker nodes and is different than each other result of the respective results.

8. The method as recited in claim 4, wherein the plurality of heterogeneous computations produce the respective results at a plurality of different times.

9. The method as recited in claim 4, wherein generating the aggregate result comprises selecting a maximum result of the respective results, selecting a minimum result of the respective results, generating a mean value or a median value based on the respective results, selecting an earliest result of the respective results, selecting a majority result of the respective results, or generating a concatenation of the respective results.

10. A system, comprising:

a plurality of computing devices comprising a plurality of processors and a plurality of memories, wherein the memories stores program instructions, and wherein the program instructions are executable by the processors to;

concurrently perform a plurality of heterogeneous computations based on a same set of input data for individual ones of the plurality of computing devices, wherein different ones of the computing devices perform different respective computational specifications to solve a same problem using the same set of input data to produce respective results, and wherein the respective computational specifications to solve the same problem comprise;

same respective algorithms configured to be concurrently implemented using the same set of input data by different types of computing platforms or processors of the different ones of the worker nodes; and

generate an aggregate result based at least on the respective results produced using the same set of input data.

11. The system as recited in claim 10, wherein the plurality of computing devices implement a master node and a plurality of worker nodes, wherein the program instructions are executable by the processors to:

distribute a plurality of computational specifications from the master node to the plurality of worker nodes, wherein the plurality of computational specifications define the plurality of heterogeneous computations, and wherein, in concurrently performing the plurality of heterogeneous computations based on the set of input data, the program instructions are executable by the processors to interpret or execute the plurality of computational specifications.

12. The system as recited in claim 11, wherein the plurality of computational specifications comprise one or more sets of executable instructions, one or more sets of interpretable instructions, or one or more service requests.

13. The system as recited in claim 11, wherein, in concurrently performing the plurality of heterogeneous computations based on the set of input data, the program instructions are executable by the processors to load the computational specifications and the set of input data into a plurality of specification interpreters.

14. The system as recited in claim 10, wherein the program instructions are executable by the processors to:

cause a plurality of computational specifications to be presented to a user in an interface for a heterogeneous computation marketplace; and

receive a selection of individual ones of the computational specifications from the user;

wherein the plurality of heterogeneous computations are concurrently performed based on the selection of individual ones of the computational specifications.

15. The system as recited in claim 10, wherein the aggregate result comprises a maximum result of the respective results, a minimum result of the respective results, a mean value or a median value based on the respective results, an earliest result of the respective results, a majority result of the respective results, or a concatenation of two or more of the respective results.

16. A non-transitory computer-readable storage medium storing program instructions computer-executable to perform:

executing a plurality of concurrent computations, wherein individual ones of the plurality of concurrent computations are based on a set of input data and on a corresponding computational specification, and wherein different ones of the computational specifications are used to solve a same problem to produce respective results using the same set of input data, and wherein at least one of the concurrent computations is executed using different instructions than other ones of the concurrent computations, and wherein the different ones of the computational specifications to solve the same problem comprise;

same respective algorithms configured to be concurrently implemented using the same set of input data by different types of computing platforms or processors of the different ones of the worker nodes; and

generating an aggregate result based at least on the respective results produced using the same set of input data.

17. The non-transitory computer-readable storage medium as recited in claim 16, wherein each of the corresponding computational specifications comprise one or more sets of executable instructions, one or more sets of interpretable instructions, or one or more service requests.

18. The non-transitory computer-readable storage medium as recited in claim 16, wherein implementing the plurality of concurrent computations comprises using a plurality of specification interpreters to interpret or execute the computational specifications to produce the respective results based on the set of input data.

19. The non-transitory computer-readable storage medium as recited in claim 16, wherein individual ones of the plurality of concurrent computations process all of the set of input data to produce the respective results.

20. The non-transitory computer-readable storage medium as recited in claim 16, wherein generating the aggregate result comprises selecting a maximum result of the respective results, selecting a minimum result of the respective results, generating a mean value or a median value based on the respective results, selecting an earliest result of the respective results, selecting a majority result of the respective results, or generating a concatenation of the respective results.