SGL: Towards a Bridging Model for Heterogeneous Hierarchical Platforms

• BSP models performance by accounting for computation, processor count, communication, and synchronization in supersteps, supporting tractable performance prediction.The passage describes BSP as a bridge between parallel algorithms and hardware architectures.Source: §1 · p. 2
• SGL generalizes BSML toward hierarchical architectures and replaces its many-to-many communication relation with simpler one-to-all and all-to-one primitives.Source: §1 · p. 2
• SGL is presented imperatively, unlike BSML’s functional language, but the paper says this distinction matters less than its other differences.BSML provides four operations and derives performance from program semantics and host BSP parameters.Source: §1 · p. 2
• SGL generalizes the two-level DMML design to potentially more machine levels, while restricting the interface by avoiding the general put operator.The authors note that an exact comparison between the models remains to be done.Source: §1 · p. 2
• SGL can emulate BSP communication phases through gather, sequential reordering, and scatter, while native support for horizontal communication remains under analysis.Automatic conversion of gather-reorder-scatter sequences to put or send-receive operations is beyond the paper's scope.Source: §1 · p. 2
• Unlike flat BSP, SGL parameters account for machine computation and communication performance, helping identify potential bottlenecks in hierarchical machines.The cost model can also help hardware vendors assess whether a technology suits a particular machine.Source: §1 · pp. 2–3

2 Motivations

• The authors frame their design against the changing assumption of flat parallel hardware as systems add multicore processors, multiple racks, and heterogeneous components.Source: §2 · p. 3
• Flat BSP is difficult to reconcile with divide-and-conquer algorithms such as Strassen multiplication and quadtree methods.Source: §2 · p. 3
• The move from scaling out to scaling up computing power, using multithreaded cores, multicore CPUs, Cell processors, and GPUs, motivates models for heterogeneous architectures.Source: §2 · p. 3
• Hierarchical machines share communication resources within levels but not across them, making the flat BSP cost model unsuitable for their structure.Source: §2 · p. 3
• SGL realizes a Multi-BSP-style programming model for heterogeneous systems using a tree-structured machine and scatter, pardo, and gather primitives.Source: §2 · pp. 3–4
• SGL semantics determine data distribution across the architecture tree, placing granularity and load balancing under program control, but this capability is not tested or described here.Source: §2 · p. 4

3.1 The SGL computer or abstract machine

• The abstract machine consists of sequential processors, each with a computation element and memory, arranged as masters and children or as leaf-workers.The model includes sequential, master-with-workers, and hierarchical machines.Source: §3.1 · p. 4

3 The SGL model

• SGL adds hierarchical topology to processor sets, while allowing flat BSP/PRAM processor arrangements to be simulated and machines of any hierarchical shape.A system has one root-master; masters coordinate their children, and each worker is controlled by one master.Source: §3.1 · pp. 4–5, §3 · p. 4

3.2 Execution model

• An SGL execution is a sequence of supersteps: the master scatters data, children compute asynchronously, results are gathered, and the master computes locally.A child’s computation may itself consist of supersteps; whether children are used depends on communication, synchronization, computation, and load-balancing parameters.Source: §3.2 · pp. 5–6

3.3 Cost model

• A superstep’s cost combines scatter and gather communication with parallel child computation and master computation, without overlap between the master’s local work and its children’s work.The total algorithm cost sums its sequential supersteps; child computation times combine by maximum.Source: §3.3 · p. 6

3.4 Parameters and detailed cost formulae

• SGL estimates communication with a linear bandwidth-and-synchronization model and local computation from instruction counts and processor speeds, with parameters that can vary by hierarchy level.The parameters include latency, directional communication gaps, words transferred, processor work, computation speed, and child count; the model supports heterogeneous architectures.Source: §3.3 · p. 6, §3.4 · pp. 6–7

4 Programming model

• SGL is an imperative language whose precise definition is given through operational semantics.It enriches the basic imperative language IMP to define a deterministic parallel programming language.Source: §4 · p. 7, §4.1 · p. 7

4.1.1 Syntax

• SGL values include integers, booleans, and arrays, with vectors of vectors supporting work blocks distributed among workers.The syntax includes scalar, vector, and vector-of-vector expressions, plus sequential statements and the three parallel primitives.Source: §4.1.1 · pp. 7–8

4.1 Operational semantics

• The operational semantics defines the meaning of SGL’s parallel statements, including scatter, pardo, and gather, alongside classical sequential constructs.The parallel primitives transfer vectors or vectors of vectors between a master and its children; gather inverts scatter.Source: §4.1.1 · pp. 7–8

4.1.2 Environments

• An environment maps locations to values, and the relative position identifies the master as 0 and each child by its position.The position is the recursive analogue of BSP’s or MPI’s pid.Source: §4.1.2 · p. 8

5 Experimentation

• The cluster is represented by a two-level SGL machine, with computation and communication parameters measured or estimated for the chosen hierarchy.The machine has 16 two-CPU nodes; the model uses measured c, l, and g parameters and algorithm-specific w quantities.Source: §5 · pp. 9–10

5.1 Parameter measurement

• Flat BSP would raise root-master-to-worker communication cost by nearly 0.4 ns/32 b; SGL models node and core networks separately.The reported g values are 3.01 ns/32 b for flat BSP, versus g↓ = 2.63 ns/32 b and g↑ = 2.68 ns/32 b in SGL.Source: §5.1 · pp. 10–11, Table 2 · p. 10, Table 3 · p. 11

5.2 Algorithms

• The tested basic algorithms are reduction, prefix reduction (scan), and sorting, implemented by hand and evaluated against predicted run times as data sizes increase.The study also computes speed-up and parallel efficiency.Source: §5.2 · p. 11
• Across reduction, scan, and sorting tests, the authors report simple SGL implementations, reliable cost-model predictions, and no intrinsic programming overhead.For scan, predictions are within a few percent, with discrepancies increasing alongside communication cost or processing units; sorting estimates fall below observations at higher local computation costs.Source: §5.2 · p. 11, §5.2.2 · p. 13, §5.2.3 · p. 16

5.2.1 Parallel reduction

• For reduction, each worker computes a local product and the master gathers child products to compute the final product; measured and predicted times nearly match.The prediction uses machine parameters measured independently of the algorithm.Source: §5.2.1 · pp. 11–13, Figure 5 · p. 12

5.2.2 Parallel scan

• The scan performs local scans, gathers worker endpoints for a master scan, then scatters offsets for workers to complete their results.Measured performance predictions are within a few percent; discrepancies increase with communication cost or processing-unit count, and more cores per processor show greater variability.Source: §5.2.2 · p. 13, Figure 6 · p. 13

5.2.3 Parallel sorting

• The PSRS sorting algorithm samples locally, selects and broadcasts pivots, redistributes partitions, and merges them; prediction error grows with local computation cost.The theoretical estimate is lower than observed execution times; the implementation also includes a node-to-node horizontal communication optimization under formal investigation.Source: §5.2.3 · pp. 13–16

5.3 Speed-up and efficiency

• Core-level scale-out is more efficient than node-level scale-out, which the authors attribute to more expensive node-level communication.Figure 8 illustrates the acceleration results from Tables 4 and 5.Source: §5.3 · p. 17, Table 4 · p. 17, Table 5 · p. 17

6 Conclusions

• SGL’s contribution is applying BSP to recursive, hierarchical, heterogeneous machines while replacing point-to-point messages with logically centralized communications.The authors do not claim that scatter-gather operations themselves are novel.Source: §6 · pp. 17–18
• SGL adapts BSML to hierarchical machines, replacing its general put primitive with scatter and gather operations.The authors describe put as a possible optimized implementation rather than a primitive.Source: §6 · p. 18
• SGL’s initial experiments indicate clean semantics, simplified programming of BSP-like algorithms, and dependable performance measurement.The authors identify implicit horizontal communication for operations such as sample sort or bucket sort as an open problem.Source: §6 · p. 18
• The authors argue that SGL’s reduced expressiveness for message-passing structures is necessary for software reliability and coherent with recursive structures.They expect existing knowledge of algorithms for cost-explicit models to yield solutions to the horizontal-communication problem.Source: §6 · p. 18

7 Future work

• Planned implementation work includes an MPI/OpenMP operations library, an SGL compiler, performance prediction, and optimizations based on the model.The optimization plans include the fundamental equation Ttotal = Tcomp + Tcomm −Toverlap.Source: §7 · p. 18
• The authors plan a compiler from domain-specific source languages without explicit parallel constructs and support for horizontal child-to-child communication.Horizontal communication could be treated as implicit semantics or as an execution optimization.Source: §7 · p. 18
• These development plans assume SGL can be compiled and executed with a variable machine view that more or less matches the physical architecture.A quad-core-based network of bi-processors could be viewed as an SGL computer with one, two, or three levels.Source: §7 · pp. 18–19
• Technical investigations include horizontal and vertical load balancing, pipelining or overlap, algorithms using horizontal communication, and modeling memory size.The list also includes extended implementations for accelerators and fault tolerance.Source: §7 · p. 19