PARALLELIZATION OF NUMERIC OPTIMIZERS

• US 20200133676A1
• Filed: 10/29/2018
• Published: 04/30/2020
• Est. Priority Date: 10/29/2018
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Peng, Chen, Richard, Hu, Shaohan, Pistoia, Marco, Gunnels, John A., Mezzacapo, Antonio
• Granted Patent: US 10,713,055 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/903 Querying for retrieval from the web G06F16/953
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 9/3822 Parallel decoding, e.g. parallel decode units
• CPC Class Codes: G06F 9/3881 Arrangements for communication of instructions and data
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications

Abstract

A method for parallelization of a numeric optimizer includes detecting an initialization of a numeric optimization process of a given function. The method computes a vector-distance between an input vector and a first neighbor vector of a set of neighbor vectors. The method predicts, using the computed vector-distance, a subset of the set of neighbor vectors. The method pre-computes, in a parallel processing system, a set of evaluation values in parallel, each evaluation value corresponding to one of the subset of the set of neighbor vectors. The method detects a computation request from the numeric optimization process, the computation request involving at least one of the set of evaluation values. The method supplies, in response to receiving the computation request, and without performing a computation of the computation request, a parallelly pre-computed evaluation value from the set of evaluation values to the numeric optimization process.

Claims

1. A method comprising:

detecting an initialization of a numeric optimization process of a given function;

computing a vector-distance between an input vector and a first neighbor vector of a set of neighbor vectors;

predicting, using the computed vector-distance, a subset of the set of neighbor vectors;

pre-computing, in a parallel processing system, a set of evaluation values in parallel, each evaluation value corresponding to one of the subset of the set of neighbor vectors;

detecting a computation request from the numeric optimization process, the computation request involving at least one of the set of evaluation values; and

supplying, in response to receiving the computation request, and without performing a computation of the computation request, a parallelly pre-computed evaluation value from the set of evaluation values to the numeric optimization process.

2. The method of claim 1, detecting the initialization of the numeric optimization process further comprising:

sensing a trigger through an application programming interface.

3. The method of claim 1, wherein the parallel processing system is a multi-core processor.

4. The method of claim 1, further comprising:

storing the set of evaluation values and the corresponding subset of the set of neighbor vectors in a database.

5. The method of claim 4, further comprising:

detecting an initialization of a second computation of the numeric optimization process; and

removing, in response to detecting an initialization of the second computation, the stored set of evaluation values and the corresponding subset of the set of neighbor vectors from the database.

6. The method of claim 1, pre-computing the set of evaluation values further comprising:

inputting the set of neighbor vectors into the given function to generate the set of evaluation values.

7. A computer usable program product comprising a computer-readable storage device, and program instructions stored on the storage device, the stored program instructions comprising:

program instructions to detect an initialization of a numeric optimization process of a given function;

program instructions to compute a vector-distance between an input vector and a first neighbor vector of a set of neighbor vectors;

program instructions to predict, using the computed vector-distance, a subset of the set of neighbor vectors;

program instructions to pre-compute, in a parallel processing system, a set of evaluation values in parallel, each evaluation value corresponding to one of the subset of the set of neighbor vectors;

program instructions to detect a computation request from the numeric optimization process, the computation request involving at least one of the set of evaluation values; and

program instructions to supply, in response to receiving the computation request, and without performing a computation of the computation request, a parallelly pre-computed evaluation value from the set of evaluation values to the numeric optimization process.

8. The computer usable program product of claim 7, wherein the computer usable code is stored in a computer readable storage device in a data processing system, and wherein the computer usable code is transferred over a network from a remote data processing system.

9. The computer usable program product of claim 7, wherein the computer usable code is stored in a computer readable storage device in a server data processing system, and wherein the computer usable code is downloaded over a network to a remote data processing system for use in a computer readable storage device associated with the remote data processing system.

10. The computer usable program product of claim 7, program instructions to detect the initialization of the numeric optimization process further comprising:

program instructions to sense a trigger through an application programming interface.

11. The computer usable program product of claim 7, wherein the parallel processing system is a multi-core processor.

12. The computer usable program product of claim 7, the stored program instructions further comprising:

program instructions to store the set of evaluation values and the corresponding subset of the set of neighbor vectors in a database.

13. The computer usable program product of claim 12, the stored program instructions further comprising:

program instructions to detect an initialization of a second computation of the numeric optimization process; and

program instructions to remove, in response to detecting an initialization of the second computation, the stored set of evaluation values and the corresponding subset of the set of neighbor vectors from the database.

14. The computer usable program product of claim 7, program instructions to pre-compute the set of evaluation values further comprising:

program instructions to input the set of neighbor vectors into the given function to generate the set of evaluation values.

15. A computer system comprising a processor, a computer-readable memory, and a computer-readable storage device, and program instructions stored on the storage device for execution by the processor via the memory, the stored program instructions comprising:

program instructions to detect an initialization of a numeric optimization process of a given function;

program instructions to compute a vector-distance between an input vector and a first neighbor vector of a set of neighbor vectors;

program instructions to predict, using the computed vector-distance, a subset of the set of neighbor vectors;

program instructions to pre-compute, in a parallel processing system, a set of evaluation values in parallel, each evaluation value corresponding to one of the subset of the set of neighbor vectors;

program instructions to detect a computation request from the numeric optimization process, the computation request involving at least one of the set of evaluation values; and

program instructions to supply, in response to receiving the computation request, and without performing a computation of the computation request, a parallelly pre-computed evaluation value from the set of evaluation values to the numeric optimization process.

16. The computer system of claim 15, program instructions to detect the initialization of the numeric optimization process further comprising:

program instructions to sense a trigger through an application programming interface.

17. The computer system of claim 15, the stored program instructions further comprising:

program instructions to store the set of evaluation values and the corresponding subset of the set of neighbor vectors in a database.

18. The computer system of claim 17, the stored program instructions further comprising:

program instructions to detect an initialization of a second computation of the numeric optimization process; and

program instructions to remove, in response to detecting an initialization of the second computation, the stored set of evaluation values and the corresponding subset of the set of neighbor vectors from the database.

19. The computer system of claim 15, program instructions to pre-compute the set of evaluation values further comprising:

program instructions to input the set of neighbor vectors into the given function to generate the set of evaluation values

20. The computer system of claim 15, wherein the parallel processing system is a multi-core processor.