RedLib — Quick Start

Background on the RedLib reduction library of PARCutils, with examples illustrating its features.

1. Framework design and implementation

1.1 Why reductions?

In many parallel computations, each parallel component produces a partial result that must be integrated with the others to compute the final outcome. This integration is called a reduction. As multi-core devices have become ubiquitous, shared-memory parallel computing is predominant, and reductions have long been exploited in parallel systems.

1.2 Design principles of RedLib

The framework emphasises modifiability and code reuse, basing the mechanism on a Reducible class and a base Reduction interface. Every reduction class — whether provided by RedLib or written by a developer — implements the Reduction interface:

public interface Reduction<E> {
    public E reduce(E first, E second);
}

RedLib’s features aim to match the performance of hand-written implementations (no overhead penalties): reusable implementations promoting code reuse; relational algebraic operations (union, intersection of sets) for complex reductions; avoidance of state variables and shared objects so implementations work in parallel; support for nesting reduction objects on dictionary types; and generic <Key, Value> pairs for a wide range of data.

1.3 Categories of implemented reductions

Scalar/simple reductions operate on primitive types: Sum, Multiplication, Average, Minimum, Maximum (Integer, Long, Short, Float, Double, BigInteger, BigDecimal); BitwiseAND/OR/XOR (Boolean, Byte, Integer, Short); AND/OR/XOR (Boolean). Example:

public class FloatAverage implements Reduction<Float> {
    public Float reduce(Float first, Float second) {
        return (first + second) / 2.0f;
    }
}

Collections/aggregate reductions operate on aggregate types using generics — union and intersection of Collections and Sets:

public class SetUnion<T> implements Reduction<Set<T>> {
    public Set<T> reduce(Set<T> first, Set<T> second) {
        for (T t : second) first.add(t);   // disregards duplicates
        return first;
    }
}

Map/dictionary reductions operate on dictionary types using generic <Key, Value> pairs in two stages: group elements by key, then reduce elements sharing a key into one. Reductions here can nest other reduction objects for the second stage:

public class MapUnion<K, V> implements Reduction<Map<K, V>> {
    private Reduction<V> reducer;
    MapUnion(Reduction<V> r) { reducer = r; }
    public Map<K, V> reduce(Map<K, V> first, Map<K, V> second) {
        // for each key in second, merge into first using reducer
        return first;
    }
}

1.4 Nesting reductions

Reductions on convoluted high-level structures (maps of maps) are cumbersome and error-prone to implement by hand and hurt readability. RedLib lets programmers nest reduction operations on the dictionary category, with generic types providing runtime flexibility — reducing the required code to one or two lines.

2. RedLib examples

2.1 WordCount

This application counts the frequency of patterns across documents. Each parallel task processes a document and returns a map of <Pattern, Frequency>; results are combined by summing the values for each pattern. A hand-written merge spans many lines; with RedLib it is two:

import pu.RedLib.*;
...
MapUnion<String, Integer> reducer = new MapUnion<>(new IntegerSum());
reducer.reduce(finalResult, secondMap);

An IntegerSum is nested inside a MapUnion, so the inner operation sums values sharing a key. To take the maximum instead, only the nested instance changes to IntegerMaximum.

2.2 RankedInvertedIndex

This application lists the documents containing user-specified words and the per-document frequencies — common in web search ranking. Each task returns a map of <Word, <Document, Frequency>>, and the final reduction has three layers: union of the outer maps, union of the inner <Document, Frequency> maps, and the maximum frequency where threads investigated the same document. With RedLib:

import pu.RedLib.*;
...
Reduction<Map<String, Map<String, Integer>>> reducer =
    new MapUnion<String, Map<String, Integer>>(
        new MapUnion<String, Integer>(new IntegerMaximum()));
reducer.reduce(finalResult, secondMap);

Reduction layers nest into each other, with the innermost layer performed by IntegerMaximum. Because every RedLib reduction can be declared as its base Reduction interface, polymorphism combined with nestable reductions gives programmers runtime flexibility in choosing operations.