ADAPTIVE PARALLEL DATA PROCESSING

• US 20120311581A1
• Filed: 05/31/2011
• Published: 12/06/2012
• Est. Priority Date: 05/31/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Balmin, Andrey, Beyer, Kevin Scott, Ercegovac, Vuk, Vernica, Rares
• Granted Patent: US 8,954,967 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Described herein are methods, systems, apparatuses and products for adaptive parallel data processing. An aspect provides providing a map phase in which at least one map function is applied in parallel on different partitions of input data at different mappers in a parallel data processing system; providing a communication channel between mappers using a distributed meta-data store, wherein said map phase comprises mapper data processing adapted responsive to communication with said distributed meta-data store; and providing data accessible by at least one reduce phase node in which at least one reduce function is applied. Other embodiments are disclosed.

Claims

1. A computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to provide a map phase in which at least one map function is applied in parallel on different partitions of input data at different mappers in a parallel data processing system;

computer readable program code configured to provide a communication channel between mappers using a distributed meta-data store, wherein said map phase comprises mapper data processing adapted responsive to communication with said distributed meta-data store; and

computer readable program code configured to provide data accessible by at least one reduce phase node in which at least one reduce function is applied.

2. The computer program product according to claim 1, further comprising:

computer readable program code configured to provide local combining at a mapper using hashing for frequently occurring mapper output pairs via maintaining a cache of partial aggregates.

3. The computer program product according to claim 2, wherein to provide local combining further comprises:

for each mapper output pair, probing the cache with a key of the mapper output pair;

on a cache hit, applying a combine function for the mapper output pair and a cached value, a result being stored back into the cache; and

on a cache miss, creating a new entry for a mapper output pair in said cache;

said computer program product further comprising;

computer readable program code configured to, responsive to determining the cache has reached a size limit, output a mapper output pair based on a cache replacement policy; and

computer readable program code configured to, responsive to determining that there is no more input for a mapper, scan the cache and write all mapper output pairs for the mapper.

4. The computer program product according to claim 3, wherein the cache replacement policy is selected from:

no replacement and least recently used.

5. The computer program product according to claim 1, wherein to provide a map phase further comprises utilizing adaptive mappers, wherein an adaptive mapper takes zero or more splits, adapts to runtime conditions, and decides when to take a given split based on optimization of job performance.

6. The computer program product according to claim 5, wherein meta-data of said splits is stored in said distributed meta-data store, and further wherein adaptive mappers compete to lock said splits.

7. The computer program product according to claim 5, wherein an adaptive mapper is configured to recover from failure;

and further wherein an adaptive mapper is configured to reprocess one or more splits claimed by another, failed adaptive mapper.

8. The computer program product according to claim 5, wherein an adaptive mapper is configured to take into consideration potential failure when taking said zero or more splits.

9. The computer program product according to claim 2, wherein to provide local combining further comprises providing local combining on de-serialized data.

10. The computer program product according to claim 1, further comprising computer readable program code configured to sample mapper output independently at a mapper and communicate to said distributed meta-data store to achieve a coordinated global sampling requirement.

11. The computer program product according to claim 9, further comprising computer readable program code configured to, responsive to the global sampling requirement being met, elect a leader mapper to aggregate all samples.

12. The computer program product according to claim 10, further comprising computer readable program code configured to provide adaptive partitioning to determine a partitioning function in parallel with mappers applying mapping;

wherein mappers co-ordinate to determine the partitioning function based on the sampling via communication with the distributed meta-data store.

13. The computer program product according to claim 9, further comprising computer readable program code configured to utilize sampling of mapper output to determine an optimal cache size and replacement policy for combining

15. The method according to claim 13, further comprising:

providing local combining at a mapper using hashing for frequently occurring mapper output pairs via maintaining a cache of partial aggregates.

17. The method according to claim 15, wherein the cache replacement policy is selected from:

no replacement and least recently used.

18. The method according to claim 13, wherein providing local combining further comprises providing local combining on de-serialized data.

19. The method according to claim 13, further comprising sampling mapper output independently at a mapper and communicating to said distributed meta-data store to achieve a coordinated global sampling requirement.

20. The method according to claim 18, further comprising:

responsive to the global sampling requirement being met, electing a leader mapper to aggregate all samples; and

providing adaptive partitioning to determine a partitioning function in parallel with mappers applying mapping;

wherein mappers co-ordinate to determine the partitioning function based on the sampling via communication with the distributed meta-data store.

14. A method comprising:

providing a map phase in which at least one map function is applied in parallel on different partitions of input data at different mappers in a parallel data processing system;

providing a communication channel between mappers using a distributed meta-data store, wherein said map phase comprises mapper data processing adapted responsive to communication with said distributed meta-data store; and

providing data accessible by at least one reduce phase node in which at least one reduce function is applied.

16. The method according to claim 14, wherein providing local combining further comprises:

for each mapper output pair, probing the cache with a key of the mapper output pair;

on a cache hit, applying a combine function for the mapper output pair and a cached value, a result being stored back into the cache; and

on a cache miss, creating a new entry for a mapper output pair in said cache;

said method further comprising;

responsive to determining the cache has reached a size limit, outputting a mapper output pair based on a cache replacement policy; and

responsive to determining that there is no more input for a mapper, scanning the cache and writing all mapper output pairs for the mapper.

21. A system comprising:

at least one processor; and

a memory device operatively connected to the at least one processor;

wherein, responsive to execution of program instructions accessible to the at least one processor, the at least one processor is configured to;

provide a map phase in which at least one map function is applied in parallel on different partitions of input data at different mappers in a parallel data processing system;

provide a communication channel between mappers using a distributed meta-data store, wherein said map phase comprises mapper data processing adapted responsive to communication with said distributed meta-data store; and

provide data accessible by at least one reduce phase node in which at least one reduce function is applied.