Systems and methods of improving parallel functional processing

Patent metadata

Field	Value
Publication number	US-10747571-B2
Application number	US-201815966149-A
Country	US
Kind code	B2
Filing date	Apr 30, 2018
Priority date	Aug 10, 2015
Publication date	Aug 18, 2020
Grant date	Aug 18, 2020

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.

First claim

What is claimed is:

1. A computer-implemented method comprising:
transforming, by at least one processor of a functional processing pipeline running on multiple processors, a free monoid over strings into a free monoid over tuples including at least one key-value pair in each tuple;
merging, by two or more processors of the functional processing pipeline running on multiple processors, the nested free monoid over tuples into one free monoid over tuples, thereby reducing a nesting depth of the nested free monoid over tuples;
transforming, by two or more processors of the functional processing pipeline running on multiple processors, one element in each tuple of the one free monoid over tuples into a list of one element in a free monoid over tuples with an embedded list element;
merging, by two or more processors of the functional processing pipeline running on multiple processors, consecutive tuples of the free monoid over tuples with the embedded list element; and
transforming, by at least one processor of a functional processing pipeline running on multiple processors, a plurality of list values into a single value based on a parameterized operation.

2. The method of claim 1 , wherein the transforming a free monoid over strings into a free monoid over tuples including at least one key-value pair in each tuple, the merging the nested free monoid over tuples into one free monoid over tuples, the transforming one element in each tuple of the one free monoid over tuples into a list of one element in a free monoid over tuples with an embedded list element, the merging consecutive tuples of the free monoid over tuples with the embedded list element, and the transforming a plurality of list values into a single value based on a parameterized operation are categorial functions, and further comprising:
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 transforming a free monoid over strings into a free monoid over tuples including at least one key-value pair in each tuple 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 transforming a free monoid over strings into a free monoid over tuples including at least one key-value pair in each tuple 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 transforming one element in each tuple of the one free monoid over tuples into a list of one element in a free monoid over tuples with an embedded list element 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 , wherein the merging consecutive tuples of the free monoid over tuples with the embedded list element further comprises, 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 , wherein the parameterized operation applied by the transforming a plurality of list values into a single value based on a parameterized operation is summation.

9. The method of claim 1 , further comprising transforming 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 comprising:
applying, by two or more processors of the functional processing pipeline running on multiple processors, the transforming a free monoid over strings into a free monoid over tuples including at least one key-value pair in each tuple to a plurality of free monoids over strings;
generating, by two or more processors of the functional processing pipeline running on multiple processors, a nested free monoid over tuples;
sorting, by two or more processors of the functional processing pipeline running on multiple processors, the free monoid over tuples or the free monoid over tuples with the embedded list element; and
transforming, by at least one processor of a functional processing pipeline running on multiple processors, 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 11 , wherein the sorting the free monoid over tuples or the free monoid over tuples with the embedded list element 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 a set of files as input and arranging the files as a free monoid over strings.

14. 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.

15. A non-transitory computer readable storage medium impressed with computer program instructions for programming one or more processors, which when executed on the processors, cause the processors to perform operations comprising:
transforming, by at least one processor of a functional processing pipeline running on multiple processors, a free monoid over strings into a free monoid over tuples including at least one key-value pair in each tuple;
merging, by two or more processors of the functional processing pipeline running on multiple processors, the nested free monoid over tuples into one free monoid over tuples, thereby reducing a nesting depth of the nested free monoid over tuples;
transforming, by two or more processors of the functional processing pipeline running on multiple processors, one element in each tuple of the one free monoid over tuples into a list of one element in a free monoid over tuples with an embedded list element;
merging, by two or more processors of the functional processing pipeline running on multiple processors, consecutive tuples of the free monoid over tuples with the embedded list element; and
transforming, by at least one processor of a functional processing pipeline running on multiple processors, a plurality of list values into a single value based on a parameterized operation.

16. The computer readable storage medium of claim 15 , wherein the transforming a free monoid over strings into a free monoid over tuples including at least one key-value pair in each tuple, the merging the nested free monoid over tuples into one free monoid over tuples, the transforming one element in each tuple of the one free monoid over tuples into a list of one element in a free monoid over tuples with an embedded list element, the merging consecutive tuples of the free monoid over tuples with the embedded list element, and the transforming a plurality of list values into a single value based on a parameterized operation are categorial functions, and wherein the instructions cause the processors to perform operation further comprising applying a plurality of instances of a composition-operator to compose the categorical functions to yi

Assignees

• Salesforcecom Inc

Inventors

• Fuchs Matthew

Classifications

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F9/46 Primary

  Multiprogramming arrangements · CPC title