| Version 4 (modified by emoken, 3 weeks ago) |
|---|
A gentle introduction to GoG
What is GoG
A GoG (Generator of Generators) is a special generator to produce generators with some dependencies. For example, GoG prefixes generates all prefixes of a given generator, in which the generated prefixes have the dependency that they are prefixes of the given generator. Also, a GoG performs optimization of nested reductions on the generated generators, in which it exploits knowledge of nice theorems of program calculation. Thus, users can receive benefit from program calculation implicitly.
Features of GoG
Features of GoG are summarized below.
- Index-free programming for various production of dependent generators.
Various GoGs are provided to generate generators with popular dependencies, such as prefixes, suffixes, subsets, and so on. The use of GoG enables users to generate dependent generators without using indices. The removal of explicit use of indices leads to maintainable and readable programs.
- Non-trivial optimization of nested reductions based on program calculation.
A GoG performs computations of nested reductions, rather than a flat reduction the simple generator does. Equipped with an optimization mechanism exploiting knowledge of calculation theorems, it optimizes the nested reductions non-trivially. Precisely saying, checking application conditions of theorems against the parameter operators of the nested reductions before executing them, it dispatches a suitable efficient implementation provided by the theorem to the execution of the nested reductions. Thus, we can write a naive parallel program using GoG, and get efficient execution of the naive program through the optimization mechanism of the GoG.
Example Use of GoG
Let's consider the following maximum prefix sum problem.
Given a sequence of numbers, find the maximum of sums of all prefixes.
For example, the maximum prefix sum of <| -1, 4, 3, -4, 5, -9 |> is 7, because its prefixes are <|-1|>, <|-1, 4|>, <|-1, 4, 3|>, <|-1, 4, 3, -4|>, <|-1, 4, 3, -4, 5|>, and <|-1, 4, 3, -4, 5, -9|>, and their sums are -1, 3, 6, 2, 7, and -2, respectively, and the maximum is 7. This problem was discussed once in the mailing list, but the efficient parallel program discussed there was a little complicated.
We can make an efficient parallel program using GoGs to solve the problem. It is demonstrated below. Basically, what we have to do is to write a naive parallel program using GoG, and the GoG optimizes the naive program exploiting calculation theorems.
1st Step: Generation of Prefixes by GoG
We can generate prefixes of <| -1, 4, 3, -4, 5, -9 |> using GoG prefixes as follows.
Now, px is a generator to produce all prefixes of <| -1, 4, 3, -4, 5, -9 |>. Here is a complete code to check it.
Here, Generator2 is imported to use GoG. Executing the above program, you can get the following printout.
<|<|-1|>, <|-1, 4|>, <|-1, 4, 3|>, <|-1, 4, 3, -4|>, <|-1, 4, 3, -4, 5|>, <|-1, 4, 3, -4, 5, -9|>|>
Those are actually prefixes of <| -1, 4, 3, -4, 5, -9 |>.
2nd Step: Taking Sums of Prefixes
To take all sums of prefixes, we apply SUM on the prefixes.
The sums of prefixes are obtained by the following program.
Execution of the program results in the following printout.
<|-1, 3, 6, 2, 7, -2|>
The output is actually the sums of prefixes.
3rd Step: Taking the Maximum of the Sums
Finally, we use BIG MAX to take the maximum of the sums, i.e., the answer of the problem. The complete code is as follows.
(Here, we use the explicit type annotation [\Number\] for workaround of weakness of the type system.)
Execution of the program results in the answer of the maximum prefix sum problem.
7
Final Step: Efficient Execution
Now, we have a correct naive parallel program for the maximum prefix sum problem. The rest of our concern is its efficiency. Apparently, the program is inefficient, because it generates n prefixes, and taking sums on all prefixes thus consts O(n2) for the input of length n. However, the program works with only O(n) cost owing to the optimization mechanism of the GoG. The optimization exploits the distributivity of the addition and the maximum to improve the efficiency. The correctness of the improvement is guaranteed by a calculation theorem about prefixes. The optimization mechanism is shown later.
Let's see the effect of the optimization. The following program measures execution time of the computation.
The function mpstest computes the maximum prefix sum for a randomly-generated array of the given length n. We can check the linearity of the cost by two facts: that the ratio t2/t1 of the execution times for the inputs of length 10000 and 100000 is not greater than 10, and that the computation for the input of length 100000 finishes in a practical time.
Further Step: Modification of the Program
We can solve similar problems using GoG. For example, we can compute the maximum segemnt sum using GoG segments as follows. It simply replaces prefixes with segments. The maximum segment sum of <| -1, 4, 3, -4, 5, -9 |> is 8, because the sum of the segment <|4, 3, -4, 5|> is 8, and it is the maximum.
This program also runs in linear cost, though its naive execution results in O(n3) cost.
Moreover, we can compute the maximum descending segment sum, in which only descendingly-ordered segments are considered. For example, the maximum descending segment sum of <| -1, 4, 3, -4, 5, -9 |> is 7, because segment <|4, 3|> is descending and its sum is 7. The segment <|4, 3, -4, 5|> is not descending, and is not taken into account. The following program computes the maximum descending segment sum.
Here, p = relationalPredicate(rel) creates a predicate p that returns true when every pair of conseqtive elements (a, b) satisfies the given relation rel, i.e., rel(a, b) is true. Its intuitive definition is as follow.
Thus, the predicate descending returns true when the given segment is descending.
The above program also runs with linear cost, because the predicate descending has the specific form and the GoG knows a theorem to optimize the nested reductions.
List of GoGs
prefixes
Given a generator, GoG prefixes produces all prefixes of the generator. For example,
results in the following list of prefixes.
<|<|1|>, <|1, 2|>, <|1, 2, 3|>, <|1, 2, 3, 4|>|>
suffixes
Given a generator, GoG suffixes produces all suffixes of the generator. For example,
results in the following list of prefixes.
<|<|1, 2, 3, 4|>, <|2, 3, 4|>, <|3, 4|>, <|4|>|>
segments
Given a generator, GoG segments produces all segments (continuous subsequences) of the generator. For example,
results in the following list of prefixes.
<|<|1|>, <|1, 2|>, <|1, 2, 3|>, <|1, 2, 3, 4|>, <|2|>, <|2, 3|>, <|2, 3, 4|>, <|3|>, <|3, 4|>, <|4|>|>
subs
Given a generator, GoG subs produces all subsequences of the generator. For example,
results in the following list of subsequences.
<|<|1|>, <|1, 2|>, <|1, 2, 3|>, <|1, 2, 3, 4|>, <|1, 2, 4|>, <|1, 3|>, <|1, 3, 4|>, <|1, 4|>, <|2|>, <|2, 3|>, <|2, 3, 4|>, <|2, 4|>, <|3|>, <|3, 4|>, <|4|>|>
List of Theorems
Basically, nested reductions with distributive operatos have efficient implementations of their executions. See technical reports for details.
