In the data-oriented paradigm, elements of a data structure are evaluated in parallel. Complex database queries are more realistic examples of data-oriented parallelism than parMap. A classic example is drawn from the manufacturing application domain, and is based on a relation between parts indicating that one part is made from zero or more others. The task is to list all component parts of a given part, including all the sub-components of those components etc. [Date, 1976].
Main Sub- Quantity Component Component P1 P2 2 P1 P4 4 P5 P3 1 P6 P7 8 P2 P5 3
A naïve function explode lists the components of a single part, main. For example, the result of exploding P1 in the relation above is [P2, P4, P5, P3]. The core of the query is the function explosions which explodes a sequence of parts.
type PartId = Int
type BillofMaterial = [(PartId, PartId, Int)]
explode :: BillofMaterial -> PartId -> [PartId]
explode parts main = [p | (m,s,q) <- parts, m == main,
p <- (s:explode parts s)]
explosions :: PartId -> PartId -> BillofMaterial -> [[PartId]]
explosions lo hi bom =
map (explode bom) [lo..hi]
The explosions function is inherently data parallel because the explosion of one part is not dependent on the explosion of any other. On the target Sun SPARCserver architecture, an appropriate thread granularity is to compute each explosion in parallel, but without parallelism within an explosion. This dynamic behaviour is specified by adding the following evaluation strategy which operates on the resulting list of lists. The seqList rwhnf forces all of the explosion to be computed by each thread. Subsequent sections include data-oriented strategies defined over many types including pairs, triples and square matrices.
explosions lo hi bom = map (explode bom) [lo..hi] `using` parList (seqList rwhnf)