Systems and methods of improving parallel functional processing

• US 9,990,223 B2
• Filed: 08/10/2015
• Issued: 06/05/2018
• Est. Priority Date: 08/10/2015
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Fuchs, Matthew
• Primary Examiner(s): Leroux, Etienne
• Application Number:
  US14/822,773
• Publication Number:
  US 20170046420A1
• Time in Patent Office: 1,030 Days
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• 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

The technology disclosed relates to improving parallel functional processing using abstractions and methods defined based on category theory. In particular, the technology disclosed provides a range of useful categorical functions for processing large data sets in parallel. These categorical functions manage all phases of distributed computing, including dividing a data set into subsets of approximately equal size and combining the results of the subset calculations into a final result, while hiding many of the low-level programming details. These categorical functions are extraordinarily well-ordered and have a sophisticated type system and type inference, which allows for generating maps and reducing them in an elegant and succinct way using concise and expressive programs that can significantly efficientize a whole software development process.

Claims

1. A method of improving parallel functional processing, the method including:

performing data transformations in a functional processing pipeline running on multiple processors using at least one instance or composition combining each of categorical functions in a group including PairMaker, FreeMonoidReduce, PairABtoAFMB, ReducePairs, and MonoidReduce, wherein;

the PairMaker categorical function transforms a free monoid over strings into a free monoid over tuples including at least one key-value pair in each tuple;

the FreeMonoidReduce categorical function merges a nested free monoid over tuples into one free monoid over tuples, thereby reducing a nesting depth of the nested free monoid over tuples;

the PairABtoAFMB categorical function transforms one element in each tuple of the one free monoid over tuples into list of one element in a free monoid over tuples with an embedded list element;

the ReducePairs categorical function merges consecutive tuples of the free monoid over tuples with the embedded list element; and

the MonoidReduce categorical function transforms a plurality of list values into a single value based on a parameterized operation.

2. The method of claim 1, further including applying a plurality of instances of a composition-operator to compose the categorical functions to yield at least one composed function, wherein the categorical functions satisfy a categorical composition and associative principle.

3. The method of claim 2, further including representing the composition operator by “

∥

”

.

4. The method of claim 1, wherein the PairMaker creates at least part of the tuples by combining consecutive elements of the free monoid over strings into the tuples.

5. The method of claim 1, wherein the PairMaker creates at least part of the tuples by combining a pre-determined value with each element in the free monoid over strings.

6. The method of claim 1, wherein the PairABtoAFMB categorical function converts at least one element in each tuple of the one free monoid over tuples from a single element into an embedded list element that includes one list value and accepts additional list values.

7. The method of claim 1, further including the ReducePairs categorical function, for consecutive tuples having matching key elements, consolidating the embedded list elements of the consecutive tuples into a single embedded list element holding a plurality of list values in a single consolidated tuple.

8. The method of claim 1, where in the parameterized operation applied by the MonoidReduce categorical function is summation.

9. The method of claim 1, further including using a StringParse function to transform a string into a free monoid over strings as a list of tokens.

10. The method of claim 9, further including storing the free monoid over strings in a linked list of at least key-value pairs.

11. The method of claim 1, further including in the functional processing pipeline using at least one instance of each function in a second group including FreeMonoidInject, SortList, and FreeMorphMophism, wherein:

the FreeMonoidlnject function applies the PairMaker to a plurality of free monoids over strings and to generate a nested free monoid over tuples;

the SortList function sorts the free monoid over tuples or the free monoid over tuples with the embedded list element; and

the FreeMorphMorphism function transforms tuple elements of the free monoid over tuples with the embedded list element, having a key and a single value list element, into a list of key-value pairs.

12. The method of claim 1, wherein the SortList function uses a key in each tuple element as at least part of a sort key.

13. The method of claim 1, further including an input operator that transforms data by accepting at least one data object as input and arranging string data in the data object as a free monoid over strings.

14. The method of claim 1, further including an input operator that transforms data by accepting a set of files as input and arranging the files as a free monoid over strings.

15. A non-transitory computer readable storage medium impressed with computer program instructions for programming one or more processors to improve parallel functional processing, when executed on the processors, implementing actions including:

performing data transformations in a functional processing pipeline running on multiple processors using at least one instance or composition combining each of categorical functions in a group including PairMaker, FreeMonoidReduce, PairABtoAFMB, ReducePairs, and MonoidReduce, wherein;

the PairMaker categorical function transforms a free monoid over strings into a free monoid over tuples including at least one key-value pair in each tuple;

the FreeMonoidReduce categorical function merges a nested free monoid over tuples into one free monoid over tuples, thereby reducing a nesting depth of the nested free monoid over tuples;

the PairABtoAFMB categorical function transforms one element in each tuple of the one free monoid over tuples into list of one element in a free monoid over tuples with an embedded list element;

the ReducePairs categorical function merges consecutive tuples of the free monoid over tuples with the embedded list element; and

the MonoidReduce categorical function transforms a plurality of list values into a single value based on a parameterized operation.

16. The computer readable storage medium of claim 15, further implementing actions including applying a plurality of instances of a composition-operator to compose the categorical functions to yield at least one composed function, wherein the categorical functions satisfy a categorical composition and associative principle.

17. The computer readable storage medium of claim 15, further implementing actions including in the functional processing pipeline using at least one instance of each function in a second group including FreeMonoidlnject, SortList, and FreeMorphMophism, wherein:

the FreeMonoidlnject function applies the PairMaker to a plurality of free monoids over strings and to generate a nested free monoid over tuples;

the SortList function sorts the free monoid over tuples or the free monoid over tuples with the embedded list element; and

the FreeMorphMorphism function transforms tuple elements of the free monoid over tuples with the embedded list element, having a key and a single value list element, into a list of key-value pairs.

18. A system including multiple coupled to memory, the memory loaded with computer instructions for programming multiple processors to improve parallel functional processing, when executed on the processors, implementing actions including:

performing data transformations in a functional processing pipeline running on multiple processors using at least one instance or composition combining each of categorical functions in a group including PairMaker, FreeMonoidReduce, PairABtoAFMB, ReducePairs, and MonoidReduce, wherein;

the PairMaker categorical function transforms a free monoid over strings into a free monoid over tuples including at least one key-value pair in each tuple;

the FreeMonoidReduce categorical function merges a nested free monoid over tuples into one free monoid over tuples, thereby reducing a nesting depth of the nested free monoid over tuples;

the PairABtoAFMB categorical function transforms one element in each tuple of the one free monoid over tuples into list of one element in a free monoid over tuples with an embedded list element;

the ReducePairs categorical function merges consecutive tuples of the free monoid over tuples with the embedded list element; and

the MonoidReduce categorical function transforms a plurality of list values into a single value based on a parameterized operation.

19. The system of claim 18, further implementing actions including applying a plurality of instances of a composition-operator to compose the categorical functions to yield at least one composed function, wherein the categorical functions satisfy a categorical composition and associative principle.

20. The system of claim 18, further implementing actions including in the functional processing pipeline using at least one instance of each function in a second group including FreeMonoidlnject, SortList, and FreeMorphMophism, wherein:

the FreeMonoidlnject function applies the PairMaker to a plurality of free monoids over strings and to generate a nested free monoid over tuples;

the SortList function sorts the free monoid over tuples or the free monoid over tuples with the embedded list element; and

the FreeMorphMorphism function transforms tuple elements of the free monoid over tuples with the embedded list element, having a key and a single value list element, into a list of key-value pairs.