SGL: Towards a Bridging Model for Heterogeneous Hierarchical Platforms

SGL: Towards a Bridging Model for Heterogeneous Hierarchical Platforms Chong Li1,2,∗

Gaétan Hains1,2

1

Laboratoire d’Algorithmique, Complexité et Logique (LACL) Université Paris-Est Créteil, 61 avenue du Général de Gaulle, 94010 Créteil, France 2 EXQIM S.A.S., 24 rue de Caumartin, 75009 Paris, France

arXiv:2610.33995v1 [cs.DC] 25 Oct 2026

(affiliations at the time of the work)

Abstract This paper introduces the Scatter-Gather parallel-programming and parallel-execution model in the form of a simple imperative Scatter-Gather Language (SGL). Its design is based on past experience with bulk-synchronous parallel (BSP) programming and BSP language design. SGL’s novel features are motivated by the last decade’s move towards multi-level and heterogeneous parallel architectures involving multi-core processors, graphics accelerators and hierarchical routing networks in the largest multiprocessing systems. The design of SGL is coherent with L. Valiant’s Multi-BSP while offering a programming interface that is even simpler than the primitives of Bulk-Synchronous Parallel ML (BSML). SGL appears to cover a large subset of all BSP algorithms while avoiding complex message-passing programming. Like all BSP-inspired systems, it supports predictable, portable and scalable performance. Moreover, SGL’s explicit data distribution will allow automatic or programmable loadbalancing. Keywords: programming environment; scalable parallel computing; hierarchical and heterogeneous architectures; performance prediction; bridging model; bulk-synchronous parallel; scatter-gather language; high-performance computing. Publication note. This is an author-prepared version, based on the accepted manuscript, of the article C. Li and G. Hains, “SGL: towards a bridging model for heterogeneous hierarchical platforms”, International Journal of High Performance Computing and Networking, 7(2):139–151, 2012, © Inderscience Enterprises Ltd. The definitive version is available at https://doi.org/10. 1504/IJHPCN.2012.046371.

1

Introduction

Parallel programming and data-parallel algorithms have been the main techniques supporting high-performance computing for many decades. Like all non-functional properties of software, the conversion of computing resources into scalable and predictable performance involves a delicate balance of abstraction and automation with semantic precision. With these goals in mind we apply the notion of explicit processes, because parallel speedup cannot be part of programming semantics without an explicit notion of the number of physical parallel processors. A language for parallel algorithms must not express a function from computation events to physical units (which may not be injective) but just the inverse. For bridging the gap between parallel systems and parallel algorithms, a major conceptual step was taken by Valiant (1990), who introduced his bulk-synchronous parallel (BSP) model. Inspired by complexity theory’s PRAM model of parallel computers, Valiant proposed that ∗

Corresponding author: chong.li@ieee.org; ORCID: 0000-0002-4160-7170

1

parallel algorithms be designed and measured by accounting not only for the classical balance between time and parallel space (the number of processors) but also for communication and synchronisation. A BSP computation is a sequence of so-called supersteps. Each superstep combines asynchronous local computation with point-to-point communications that are coordinated by a global synchronisation to ensure coherence and determinism. The resulting performance model is both realistic and tractable, so that researchers like McColl and Walker (1998) were able to define BSP versions of all important PRAM algorithms, implement them and verify their portable and scalable performance as predicted by the model. BSP is thus a bridging model relating parallel algorithms to hardware architectures. A well-known implementation of BSP is the Paderborn University BSP library, or PUB (Bonorden et al., 2003). This work has been extended by many similar models: LogP (Culler et al., 1993), LogGP (Alexandrov et al., 1995) for long messages, HLogGP (Bosque and Pastor, 2004) for heterogeneous processors, LogGPO (Chen et al., 2009) to account for computation-communication overlap, and the CGM model (Dehne et al., 1993). Loulergue et al. (2000) designed BS-λ as a minimal model of computation with BSP operations (an extension of the λ-calculus). BS-λ became the basis for Bulk-Synchronous Parallel ML, BSML (Loulergue, 2000, 2010), a variant of Caml. BSML offers a purely functional semantics and a simple programming interface of only four operations: mkpar to construct parallel vectors indexed by processors, proj to map them back to lists/arrays, apply to generate asynchronous parallel computation, and put to generate communication and global synchronisation from a two-dimensional processor-processor pairing. As a result, parallel performance mathematically follows from program semantics and the BSP parameters of the host architecture. By comparison with BSML, our new Scatter-Gather Language (SGL) model can be understood as: 1. a generalisation to hierarchical architectures, by breaking the restriction to a flat vector of processors; 2. a simplified set of primitives, where the “many-to-many” processor relations of put are replaced by simpler “one-to-all” and “all-to-one” relations. Our presentation of SGL is in the form of an imperative language, while BSML is a variant of ML, hence a functional language. But that last difference is less important than the above two. Among the earlier works on BSML, the grid or departmental meta-computing ML (DMML) model and language of Gava and Loulergue (2005) described a two-level BSP. Its lower level represents local parallel clusters and its top level a grid of such systems. SGL is both a generalisation of this design, for systems that have potentially more levels, and a restriction of the programming interface, by avoiding the most general communication operator put. SGL can cover lower levels inside the machines and also higher levels, for example from multi-core processors like the Nvidia Tesla or the STI Cell to giant systems like Tera-100 or Blue Gene. An analysis of the exact differences between both models remains to be done, but the experience gained on DMML will be reused for investigating and developing SGL. SGL is well adapted to BSP-like algorithms whose communication patterns are all-to-all maps, but we believe that all BSP algorithms can be programmed in SGL for the following reasons. SGL can trivially emulate any BSP communication phase by simply concentrating all messages (gather), then reordering them sequentially before sending them to their destinations (scatter). But a random “horizontal” communication pattern could also be implemented natively after having been written as a gather-reorder-scatter sequence and then automatically converted into put or send-receive operations. This kind of optimisation is beyond the scope of this paper, but we have begun analysing its possibility in the language semantics. SGL models parallel machines more precisely than BSP. SGL parameters take into consideration both the machine’s computation performance and its communication performance. SGL’s cost model can inform developers whether or not the root of a hierarchical tree-structured machine, such as a GPU cluster, can be a bottleneck. SGL can also help hardware vendors 2

measure whether a new technology can be useful for a particular machine. For example, the well-known hierarchical tree-structured parallel machine CM-5 (Leiserson et al., 1992), using a fat-tree (Leiserson, 1985) architecture for its data network, had good performance according to SGL’s communication parameters. The next section gives precise arguments that motivate our SGL model, in the context of existing similar models like BSP or LogP. Section 3 then describes the SGL model’s abstract machine, execution model and cost model, relating machine parameters to actual algorithm performance. Section 4 formally defines the programming model as the operational semantics of an imperative mini-language. Section 5 presents and analyses performance-measurement experiments for primitive algorithms. Finally, Sections 6 and 7 conclude with a summary of ongoing work and open problems related to SGL.

2

Motivations

While BSML was evolving and practical experience with BSP algorithms was accumulating, one of its basic assumptions about parallel hardware was changing. The flat view of a parallel machine as a set of communicating sequential machines remains true but is more and more incomplete. Recent supercomputers like Blue Gene/L (Almási et al., 2003) and Blue Gene/P (IBM Journal of Research and Development staff, 2008) feature multi-processors on one card, multi-core processors on one chip, multiple-rack clusters, etc. The Cell/B.E. (Kahle et al., 2005; Johns and Brokenshire, 2007), the Cell-based Roadrunner (Barker et al., 2008) and GPUs feature a master-worker architecture. Moreover, Kumar et al. (2005) observe that heterogeneous chip multiprocessors present unique opportunities for improving system throughput and reducing processor power. The trend towards green computing puts even more pressure on the optimal use of architectures that are not only highly scalable but hierarchical and non-homogeneous. During the 2000s it became obvious that models like BSP should adapt or generalise to the new variety of architectures. Yet programming simplicity and performance portability should be retained as much as possible. With these goals in mind, Valiant introduced Multi-BSP (Valiant, 2011), a multi-level variant of the BSP model, and showed how to design scalable and predictable algorithms for it; Stewart (2011) proposed a programming model for BSP with partitioned synchronisation. The main new feature of Multi-BSP is its hierarchical nature, with nested levels that correspond to the natural layers of physical architectures. In that sense it preserves the notion of explicit processes and, as we will show in this paper with our SGL design, allows us to solve three pending problems with BSP programming: 1. The flat nature of BSP is not easily reconciled with divide-and-conquer parallelism (Hains, 1998), yet many parallel algorithms (e.g., Strassen matrix multiplication, quad-tree methods) are highly artificial to program any other way than recursively. 2. BSP was designed natively to scale out with the number of processors, and it was assumed that CPU clock speeds would continue to improve. However, there are barriers to further significant improvements in operating frequency due to voltage leakage across internal chip components and heat dissipation limits (Sodan et al., 2010). As a result, parallelism is nowadays used to scale up computing power, through multithreaded cores, multi-core CPUs, Cell processors, GP-GPUs, etc. 3. We do not know how to design algorithms for nested-level systems with the original flat BSP model. Hierarchical architectures share communication resources inside every level but not between different levels. The BSP cost model is not suitable for this kind of architecture. Based on all the above developments and the last three observations, we now define the SGL model, which realises a programming model for Multi-BSP, generalises it to heterogeneous systems and yet simplifies the BSML primitives to a set of three. SGL assumes a tree-structured 3

machine and uses only the following parallel primitives: scatter (to send data from a master to its sub-machines), pardo (to request asynchronous computations from the sub-machines) and gather (to collect data back to the master). We show how to embed this model in an imperative language, how to define its operational semantics and its performance model, and how to use it to code useful algorithms (reduction, parallel scan and sorting). We then provide some initial measurements to validate its performance model, and explanations as to how it can easily adapt to heterogeneous systems. The work summarised here is initial evidence that SGL can provide both a simpler programming interface than BSML and a richer execution model, like Multi-BSP. Like BSML, SGL has explicit data layout: its semantics uniquely determines data distribution on the nodes of the architecture tree. This allows for automatic tuning on most types of modern architectures in the following sense. Exact communication-computation overlap is not expressible in a language like SGL, but granularity (resp. load balancing) is under program control because communication (resp. data layout) is explicit. This feature is neither tested nor described in this paper, but the existing literature on BSP programming makes us confident that it will be retained by SGL.

3

The SGL model

The PRAM model (Fortune and Wyllie, 1978) of parallel computation begins with a set of p sequential von Neumann machines (processors). It then connects them with a shared memory and an implicit global controller (as in a SIMD architecture). The BSP model (Valiant, 1990) relaxes the global-control and direct-memory-access hypotheses. It also begins with a set of p sequential machines but assumes asynchronous execution, except for global synchronisation barriers and point-to-point communications that complete between two successive barriers. It is common to assume that the PRAM/BSP processors are identical, but it is relatively easy to adapt algorithms to a set of heterogeneous processors with varied processing speeds. In both cases the set of processors has no structure other than its numbering from 0 to p − 1. This absence of structure on the set of processors can be traced back to the failure of a trend of research popular in the 1980s: algorithms for specific interconnect topologies, such as hypercube algorithms, systolic algorithms, rectangular-grid algorithms, etc. We trace this failure to the excessive variety of algorithms and architectures without a model to bridge the portability gap between algorithms and parallel machines. The SGL model we propose does introduce a degree of topology on the set of processors. But this topology is purely hierarchical and not intended to become an explicit factor of algorithm diversity. Just as PRAM/BSP algorithms use the p parameter to adapt to systems of all sizes, our SGL algorithms use the machine parameters to adapt to all possible systems.

3.1

The SGL computer or abstract machine

The SGL model (Fig. 1) defines a set of sequential processors, each composed of a computation element (“core”) and a memory unit. The processors are arranged in a tree structure, whose root is called a master and whose children are either masters themselves or leaf-workers. The number of children is not limited, so that the BSP/PRAM concept of a flat p-vector of processors is easily simulated in SGL. Different forms are possible: • only one worker without master: a sequential machine; • a master with workers: a parallel machine, e.g., a BSP computer; • a hierarchical machine (Fig. 2) of any shape. The logical structure of an SGL computer satisfies the following constraints: • a system has one and only one root-master; 4

Master Coordinating core Central memory

Worker

Worker

Computing core

Computing core

··· Local memory

Local memory

Figure 1: SGL abstract machine. Master

···

Master

Worker

···

Worker

Worker

Figure 2: SGL hierarchical machine. • a master coordinates its children through communication; • a worker is controlled by one and only one master (masters can be replicated by underlying libraries for fault tolerance); • communication is always between a master and its children.

3.2

Execution model

An SGL program execution is a sequence of supersteps. The initial data and the final result can be either distributed among the workers or centralised in the root-master. Each superstep is composed of four phases: 1. a scatter communication phase initiated by the master; 2. an asynchronous computation phase performed by the children (a child’s computation phase can itself be a sequence of supersteps); 3. a gather communication phase centred on the master; 4. a local computation phase on the master. With these four phases, one can usually write an SGL program recursively: if node is a master and its children are to be used then split input data into blocks; scatter data blocks; compute on individual data blocks in children (in parallel); gather children’s results; combine children’s results in master (if necessary); else compute on local data on node;

5

The choice of using (or not) children in the recursive program depends on performance parameters that combine the (known) communication costs, synchronisation costs, computation costs and load balancing.

3.3

Cost model

Like all such models, SGL’s main goal of expressing parallel algorithms requires a precise notion of the execution time of a program. We give here the mathematical form of this cost model, with the understanding that a full definition should be based on the operational semantics and will be given in a further document. The cost equations below are nevertheless sufficient for informal algorithm design and understanding, and for comparison with other parallel models. The cost of an SGL algorithm (i.e., of its execution on given input data) is the sum of the costs of its supersteps. That follows from the understanding that supersteps are executed sequentially. The cost of an individual superstep is split into two independent terms, computation cost and communication cost: Cost total =

P

Cost superstep ,

Cost superstep = Comptotal + Comm total .

Computation cost is the sum of local computation times in the children (parallel, hence combined with max) and of the local computation in the master. Addition of both terms realises the hypothesis that the master’s local work may not overlap with the work of its children. Communication cost is split into the cost of performing the scatter and the gather operations: Cost superstep = Comm scat + max Compchildren + Comm gath + Compmaster , Comm scat = Words scat × Bwidth scat + Sync, Comm gath = Words gath × Bwidth gath + Sync, Compnode = Instructions/ClkRate. Communication costs are thus estimated by a linear term similar to BSP’s g × h + L, based on machine parameters for (the inverse of) bandwidth and for synchronisation between the master and its children. As always, local computation cost is the number of executed instructions divided by the processing speed. The machine-dependent parameters can be made as abstract or concrete as desired. In other words, theoretical SGL algorithms can be investigated with respect to their asymptotic complexity classes, while portable concrete SGL algorithms can be analysed for more precise cost formulae using bytecode-like instruction counts and normalised communication parameters. Finally, SGL programs can be compiled and measured for actual performance on a given architecture. We remind the reader that, like the machine architecture, all the cost formulae above are intended to be recursive: the local computation cost on a child node can itself be an SGL algorithm cost if the machine structure is such.

3.4

Parameters and detailed cost formulae

In contrast to Multi-BSP (Valiant, 2011), concrete cost estimations and measurements use the following machine and algorithm parameters. Each level of a hierarchy can have different parameter values. • l: the latency to perform a scatter or gather synchronisation, i.e., the time to execute a 1-bit scatter or a 1-bit gather. • g: the gap; g↓ is the time interval for transmitting one word from the master to its children, and g↑ from the children to their master. We use a single g in the case of symmetric communication costs.

6

• k: the number of words to transmit; k↓ is the number of words that the master scatters to its children, and k↑ the number of words that the master gathers from its children. • w: the work, or number of local operations performed by processors; w0 is the master’s work and wi (i = 1..p) the work of child i. A parameter w without index refers to a local quantity. • c: the computation speed of processors; c0 is the time interval for performing a unit of work on the master and ci (i = 1..p) the time interval for performing a unit of work on child processor i. A parameter c without index refers to a local quantity. • p: the number of children of a master. In general the cost formulae are

Cost Master = max Cost childi + w0 × c0 + k↓ × g↓ + k↑ × g↑ + 2l, i=1..p

Cost Worker = wi × ci , which clearly covers the possibility of a heterogeneous architecture. Typically, but not necessarily, communication costs are symmetric: h

i

Cost superstep = w × c + max Cost childi + (k↓ + k↑ ) × g + 2l . i=1..p

4

Programming model

SGL’s precise definition is an imperative language, for which we now give an operational semantics.

4.1

Operational semantics

We enrich Winskel’s basic imperative language IMP (Winskel, 1993) to yield our deterministic parallel programming language, SGL. 4.1.1

Syntax

Values. Values are integers, booleans, and arrays (vectors) built of them. Vectors of vectors are necessary for building blocks of work to be scattered among workers. • n ranges over numbers Nat. • ⟨n1 , n2 , . . . , nℓ ⟩ ranges over arrays of numbers Vec, where ℓ ∈ Nat is the length of the array. • ⟨v1 , v2 , . . . , vℓ ⟩ ranges over arrays of arrays VecVec. The scatter operation takes a vector of vectors in the master and distributes it to the workers/children. The gather operation inverts this process. Locations. Imperative variables are abstractions of memory positions and are called locations. They are many-sorted, like the language’s values. • X ranges over scalar locations NatLoc, i.e., names of memory elements that store numbers. Xi=pid denotes master/children locations; X without index denotes the master location. → − • V ranges over vectorial locations VecLoc, i.e., names of memory elements that store → − → − arrays. V i=pid denotes master/children locations; V without index denotes the master location. f ranges over vector-of-vector locations VVecLoc, i.e., names of memory elements that • W store arrays of arrays.

7

Operations. • ⊙ denotes the binary operations + | − | ∗ | /; • [ ] denotes element access in a vector; • :∼ denotes data to be transferred between a master and its children (i.e., an array of arrays). Expressions. Expressions are relatively standard, with the convenience of scalar-to-vector (sequential) operations. → − • a ranges over scalar arithmetic expressions: Aexp ::= n | X | a ⊙ a | V [a] • b ranges over scalar boolean expressions: Bexp ::= true | false | a = a | a ≤ a | ¬b | b∧b|b∨b → − f [a] • v ranges over vectorial expressions: Vexp ::= ⟨a1 , a2 , . . . , aℓ ⟩ | V | v ⊙ a | v ⊙ v | W • w ranges over vector-of-vector expressions:

f VVexp ::= ⟨v1 , v2 , . . . , vℓ ⟩ | W

Statements. The language’s statements include the classical sequential constructs together with SGL’s three primitives: scatter, pardo and gather. The exact meaning of the parallel statements is defined by the semantic rules below; the definition of the other statements can be found in Li and Hains (2010). Commands c range over → − f := w | c ; c Com ::= skip | X := a | V := v | W | if b then c else c | for X from a to a do c → − | scatter w to V | scatter v to X → − − f | gather X to → | gather V to W V | pardo c | if master c else c. 4.1.2

Environments

States (or environments) are maps from imperative variables (locations) to values of the corresponding sort. Like values, they are many-sorted, and we use the following notations and definitions for them. Functions in states Σ: • σ : NatLoc → Nat, thus σ(X) ∈ Nat; → − • σ : VecLoc → Vec, thus σ( V ) ∈ Vec; f ) ∈ VecVec. • σ : VVecLoc → VecVec, thus σ(W

Here pos ∈ Pos ⊆ Nat is what we call the (relative) position: pos = 0 denotes the master position (as above), and pos = i ∈ {1..p} denotes the position of the i-th child. It is the recursive analogue of BSP’s (or MPI’s) pid. • σ : NatLoc → Pos → Nat, thus σ(Xpos ) = σpos (X) ∈ Nat; → − → − • σ : VecLoc → Pos → Vec, thus σ( V pos ) = σpos ( V ) ∈ Vec.

8

Rules for vectorial expressions. no special explanation.

The semantics of vector expressions is standard and deserves

∀i = 1..ℓ ⟨ai , σ⟩ → ni ⟨⟨a1 , a2 , . . . , aℓ ⟩, σ⟩ → ⟨n1 , n2 , . . . , nℓ ⟩ f , σ⟩ → σ(W f ) = ⟨v1 , . . . , vℓ ⟩ ⟨W

→ − → − ⟨ V , σ⟩ → σ( V ) ⟨a, σ⟩ → n

f [a], σ⟩ → vn ⟨W

⟨v, σ⟩ → ⟨n′1 , . . . , n′ℓ ⟩

⟨v1 , σ⟩ → ⟨n′1 , . . . , n′ℓ ⟩

⟨a, σ⟩ → n ∀i = 1..ℓ ⟨v ⊙ a, σ⟩ → ⟨n1 , . . . , nℓ ⟩

⟨n′i ⊙ n, σ⟩ → ni

⟨v2 , σ⟩ → ⟨n′′1 , . . . , n′′ℓ ⟩ ∀i = 1..ℓ ⟨v1 ⊙ v2 , σ⟩ → ⟨n1 , . . . , nℓ ⟩

⟨n′i ⊙ n′′i , σ⟩ → ni

(The lengths of v1 and v2 must be equal.) The rules for the other expressions are written similarly. Primitive parallel statements. In the following rules, numChd is the number of children of the processor. Scatters. → − ∀i = 1..numChd ⟨ V i :∼ vi , σ⟩ → σi′ → − ⟨scatter w to V , σ⟩ → σ ′

⟨w, σ⟩ → ⟨v1 , . . . , vℓ ⟩

⟨v, σ⟩ → ⟨n1 , . . . , nℓ ⟩ ∀i = 1..numChd ⟨Xi :∼ ni , σ⟩ → σi′ ⟨scatter v to X, σ⟩ → σ ′ Gathers. → − ⟨ V :∼ ⟨X1 , X2 , . . . , XnumChd ⟩, σ⟩ → σ ′ → − ⟨gather X to V , σ⟩ → σ ′

− → − → − f :∼ ⟨→ ⟨W V 1 , V 2 , . . . , V numChd ⟩, σ⟩ → σ ′ → − f , σ⟩ → σ ′ ⟨gather V to W Parallel. ∀i = 1..numChd ⟨c, σi ⟩ → σi′ ⟨pardo c, σ⟩ → σ ′

⟨numChd = 0, σ⟩ → true ⟨c2 , σ⟩ → σ ′ ⟨if master c1 else c2 , σ⟩ → σ ′

⟨numChd = 0, σ⟩ → false ⟨c1 , σ⟩ → σ ′ ⟨if master c1 else c2 , σ⟩ → σ ′

5

Experimentation

Now that the language’s cost model and operational semantics have been defined, we summarise some performance measurements and analyse them with respect to the cost model. The local processing speed c and the network parameters l, g can be measured on a chosen machine once the hierarchy of processors and the benchmarking setup have been defined. For a given algorithm, we can also analyse theoretically, estimate or count the w quantities. We have performed experiments to observe how the measured computation time of an SGL algorithm compares with the cost model’s prediction. The overall system has the following description:

9

Nodes CPU RAM Network

16 computing nodes (2 CPUs/node) Intel Xeon E5440 (quad-core, 2.83 GHz) 512 GB in total (4 GB/core, DDR2 667) 4X DDR InfiniBand switches (16 Gbit/s)

We build a two-level SGL abstract machine to represent this physical machine (Table 1 and Fig. 3). Table 1: Two-level SGL abstract machine for the experimental cluster. Unit

Children

Communication

Root-master Node-master Worker

16 nodes 8 cores 0

InfiniBand Front-side bus N/A

Machine

Root-master

InfiniBand 16 nodes

Node level

Node-master

···

Node-master

Front-side bus Core level

8

8

Worker · · · Worker

Worker · · · Worker

Figure 3: The two-level SGL machine for EXQIM’s cluster.

5.1

Parameter measurement

The CPUs of the computing nodes are clocked at 2.83 GHz, so that c = 0.353 ns/op for each of them. At node level, we use the collective functions MPI_Barrier for L, MPI_Scatterv for g↓ and MPI_Gatherv for g↑ of SGI’s Message Passing Toolkit (MPT 2.04). In Table 2, the first four lines were used in our experiments of SGL on a hierarchical architecture, and the last four lines are used for comparison with BSP on a flat architecture. Table 2: Node-level parameters. With SGI’s MPI implementation the cost of g increases with the number of processes, and MPI_Gatherv has a minimum around 2 ns/32 b. Nodes × cores

L (µs)

g↓ (ns/32 b)

g↑ (ns/32 b)

2 4 8 16

2×1 4×1 8×1 16 × 1

1.48 2.85 4.37 5.96

1.38 1.69 1.89 2.04

2.15 2.00 2.05 2.09

32 64 96 128

16 × 2 16 × 4 16 × 6 16 × 8

7.62 7.93 8.81 9.89

2.14 2.63 2.88 3.01

2.09 2.11 2.13 2.77

Number of procs

At the core (worker) level, we use OpenMP’s barrier for L and the C function memcpy for g. Instead of directly transferring pointers to data, we use memcpy() to copy data into different memory regions, to avoid concurrent access between CPU cores. Table 3 shows the measured core-level parameters. According to Tables 2 and 3 (see also Fig. 4), if we used flat BSP instead of the SGL model to represent our machine, the communication cost between root-master and workers would 10

g↓ (MPI_Scatterv) g↑ (MPI_Gatherv)

g (ns per 32-bit word)

3

2.5

2

1.5

0

16

32

48

64

80

96

112

128

Number of processes

Figure 4: Measurement of g in MPI (data of Table 2). Table 3: Core-level parameters. Machine

L (µs)

g (ns/32 b)

2 cores 4 cores 6 cores 8 cores

12.08 25.64 37.80 52.00

0.59 0.59 0.59 0.59

increase by nearly 0.4 ns/32 b. To represent our physical machine in BSP, we would build a 128-processor abstract machine using MPI. Under this architecture, the value of g would be max(3.01, 2.77) = 3.01 ns/32 b. In SGL, we instead built a 16-processor network at node level using MPI and an 8-processor network at core level using OpenMP. Thus the value of g↓ is 2.04 + 0.59 = 2.63 ns/32 b and the value of g↑ is 2.09 + 0.59 = 2.68 ns/32 b. This is a medium-scale but concrete example of the practical gains obtained from a hierarchical model that better fits the physical architecture.

5.2

Algorithms

We have tested SGL variants of some of the most important basic parallel algorithms: parallel reduction (with the product operation), parallel prefix reduction, also called scan (with the sum operation), and a sorting algorithm. For each one we wrote an SGL algorithm, implemented it by hand using the MPI/OpenMP operations mentioned above, and then compared the model’s predicted and observed run times for increasing data sizes. Finally, we computed speed-up and parallel-efficiency values. The three tests illustrate SGL’s relative programming simplicity on a relevant set of algorithms, give convincing evidence of the cost model’s quality, and provide initial evidence that SGL programming has no intrinsic cost overhead. 5.2.1

Parallel reduction

In Algorithm 1, each worker computes the product of its local scalar numbers. After that, the master fetches the computed products from its children and calculates the final product (annotations on the right are cost estimates for the corresponding lines). 11

2 000

Time (µs)

1 500

1 000

500

0 0

200

400

600

800

1 000

1 200

1 400

3

Data size (×10 floating-point numbers) 1 proc Predicted, 8 procs Predicted, 16 procs

2 procs (2 cores) 8 procs (2 × 4) 16 procs (4 × 4)

2 procs (2 nodes) 8 procs (4 × 2) 16 procs (8 × 2)

Figure 5: Predicted and actual execution times for SGL reduction. Algorithm 1 Parallel reduction → OUT res) Reduction(IN − src, begin 1: if master then 2: par do → res); 3: Reduction(− src, 4: end par − → 5: gather res to lst; − → 6: Product(lst, res); 7: else → res); 8: Product(− src, end

⇐ Reduction childi ⇐ p × g↑ + l ⇐ O(p) ⇐ O(n)

→ OUT res) Product(IN − src, begin 9: res := 1; − → 10: for i from 1 to len(src) do → 11: res := res ∗ − src[i]; end Line 3 is a recursive call to the algorithm, and line 8, the no-children case, is a local sequential → whose elements are the res outputs of the children. The cost of loop. Product operates on − src, the superstep is (subscripts ⟨·⟩ refer to the pseudo-code lines):

Cost Master = max Reduction childi ⟨3⟩ + O(p)⟨6⟩ × c + p⟨5⟩ × g↑ + l, i=1..p

Cost Worker = O(nworker )⟨8⟩ × c. The measurements (Fig. 5) show a nearly perfect match between measured performance and predicted performance, the latter being obtained from the cost formula with machine parameters 12

measured independently of this algorithm. 5.2.2

Parallel scan

We perform the parallel scan algorithm (Algorithm 2) in two steps: 1. Each worker performs a sequential scan. Then the master fetches the last computed element from each child. After that, it performs a sequential scan of the fetched data. 2. The master scatters the results among its children. Then each child adds the received value to its computed data. Finally, the children hold the final result. The pseudo-code is given in Algorithm 2, and the cost of the superstep is

Cost Master = max Step1 childi + O(1) × ci + max Step2 childi + O(nchildi ) × ci i=1..p

i=1..p

+ O(p) + O(p − 1) × c + p × g↑ + p × g↓ + 2 × l, Cost Worker = O(nworker ) × c. Again, the pseudo-code and the measurements (Fig. 6) support our claims that SGL is simple to use and that its performance model is reliable. Several observations can be made from this graph: the performance prediction is correct to within a few percent, and the discrepancy between prediction and observation increases with communication cost or with the number of processing units. Moreover, configurations with more cores per processor exhibit larger variability due to the local shared memory. 800

Time (µs)

600

400

200

0 0

50

100

150

200

250

300

350

400

3

Data size (×10 floating-point numbers) 1 proc Predicted, 8 procs Predicted, 16 procs

2 procs (2 cores) 8 procs (2 × 4) 16 procs (4 × 4)

2 procs (2 nodes) 8 procs (4 × 2) 16 procs (8 × 2)

Figure 6: Predicted and actual execution times for SGL scan. We now experiment with a BSP sorting algorithm in SGL. 5.2.3

Parallel sorting

Our parallel sorting algorithm (Algorithms 3 and 4) is based on parallel sorting by regular sampling, PSRS (Shi and Schaeffer, 1992), a partition-based algorithm. We could also use the algorithm of Helman et al. (1998) to improve performance. We implement this algorithm in five steps: 13

Algorithm 2 Parallel scan −→ → OUT − Step1(IN − src, mid) begin 1: if master then

par do −→ → − 3: Step1(− src, mid); −−→ −−→ 4: x := mid[len(mid)]; 5: end par −−→ 6: gather x to mid; −−→ 7: ShiftRight(mid); −−→ −−→ 8: LocalScan(mid, mid); 9: else −→ → − 10: LocalScan(− src, mid); end 2:

⇐ Step1 childi ⇐ O(1)childi ⇐ p × g↑ + l ⇐ O(p) ⇐ O(p) ⇐ O(n)

−−→ → Step2(IN mid, OUT − res) begin 11: if master then −−→ 12: scatter mid to x; 13: par do −→ − → := − 14: res mid + x; → − → 15: Step2(− res, res); 16: end par 17: else 18: skip; end

⇐ p × g↓ + l ⇐ O(nchildi ) ⇐ Step2 childi

→ OUT − → LocalScan(IN − src, res) begin −→ − → 19: res[1] := src[1]; − → 20: for i from 2 to len(src) do − → − → → 21: res[i] := res[i − 1] + − src[i]; end − → ShiftRight(INOUT lst) begin − → 22: for i from len(lst) downto 2 do − → − → 23: lst[i] := lst[i − 1]; − → 24: lst[1] := 0; end 1. Each worker performs a local sort and selects p (the number of workers) samples, which are gathered onto the root-master. 2. The root-master performs a local sort of the p2 gathered samples. Then it picks p − 1 almost equally spaced pivots from the sorted samples. 3. The root-master broadcasts these pivots to all workers. After that, each worker produces p partitions of its local data using the p − 1 pivots. Partition i holds the values that should now be moved to worker i. 14

4. The master gathers the partitions that are not already in place. 5. The master scatters the gathered partitions to its children according to the partitions’ indices. Then each worker performs a local merge of the received partitions. Algorithm 3 Parallel sorting by regular sampling, steps 0–3 Step0 1: initialise pid := 1 in each worker; 2: use parallel scan (Algorithm 2) to compute the pid of each worker; 3: set lowerPid, upperPid and maxPid in masters; → OUT − −→ Step1(IN − arr, sam) begin 4: if master then 5: par do → − −→ 6: Step1(− arr, sam); 7: end par −→ to tmp; g 8: gather − sam − − → g 9: sam := Concatenate(tmp); 10: else → 11: QuickSort(− arr); → − −→ 12: SelectSamples(− arr, sam); end → −→ OUT − Step2(IN − sam, pvt) begin −−→ 13: QuickSort(sam); −−→ −→ 14: PickPivots(sam, pvt); end → → IN − f Step3(IN − arr, pvt, OUT blk) begin 15: if master then 16: for i from 1 to numChd do → g := − 17: tmp[i] pvt; → g to − 18: scatter tmp pvt; 19: par do → f → − 20: Step3(− arr, pvt, blk); 21: end par 22: else → f → − 23: BuildPartitions(− arr, pvt, blk); end Sujithan (1996) showed that the computational cost of this algorithm is 2 np log n − log p +
p3 1 n log p and its communication cost is g p

p2 (p − 1) + n + 4l in BSP. Thus the total cost of this

algorithm implemented in SGL is 2


n p3 1 log n − log p + log p × c + p2 (p − 1) + n × G + 4 × L, p n p

where G is the sum of the g of all levels and L is the sum of the l of all levels. Our performance prediction is based on SeqSort(n) = O(n log n) for the sequential sorting algorithm and O(n/p) for the data to be transferred from one node to another after the local 15

Algorithm 4 Parallel sorting by regular sampling, steps 4–5 f OUT stay, g OUT move) Step4(IN blk, ] begin 1: if master then 2: par do f stay, g move); 3: Step4(blk, ] 4: end par 5: for i from 1 to maxPid do g 6: gather move[i] ] to tmp; 7: if i < lowerPid or i > upperPid then g 8: move[i] ] := Concatenate(tmp); 9: else g g 10: stay[i] := Concatenate(tmp); 11: else 12: for i from 1 to maxPid do 13: if i = pid then f g 14: stay[pid] := blk[pid]; 15: else f 16: move[i] ] := blk[i]; end

→ g IN move, Step5(IN stay, ] OUT − arr) begin 17: if master then → 18: scatter Bundle(move) ] to − arr; 19: par do → g := Unbundle(− 20: tmp arr); 21: for i from lowerPid to upperPid do g g 22: move[i] ] := Concatenate(tmp[i], stay[i]); → g move, 23: Step5(stay, ] − arr); 24: end par 25: else − → := MergeSort(move[pid]); 26: arr ] end sort. Our implementation includes a node-to-node horizontal communication optimisation, which we have begun to investigate formally and will add to an SGL compiler. The measurements shown in Fig. 7 lead to the same observations and explanations as above for the parallel scan. Higher local computation costs lead to a larger prediction error; in particular, our theoretical estimate is lower than the observations. The pseudo-code shows that our primitive algorithms are easily implemented in SGL. Future work will investigate SGL programming for more general algorithms. We now provide some quantification of SGL’s capacity to generate large speed-ups.

5.3

Speed-up and efficiency

We tested speed-up and efficiency using the reduction algorithm of Algorithm 1. The formulae we used are Speedupp ExecutionTime 1 Speedupp = , Efficiency p = , ExecutionTime p p

16

Time (µs)

15 000

10 000

5 000

0 0

100

200

300

400

500

600

700

800

900

1 000

3

Data size (×10 floating-point numbers) 1 proc Predicted, 8 procs Predicted, 16 procs

2 procs (2 cores) 8 procs (2 × 4) 16 procs (4 × 4)

2 procs (2 nodes) 8 procs (4 × 2) 16 procs (8 × 2)

Figure 7: Predicted and actual execution times for SGL parallel sorting by regular sampling. where p is the number of nodes (resp. cores) used. First, we fixed the size of the input data at 2 560 000 floating-point numbers and the number of cores at four per node, and varied the number of nodes from 1 to 16. The results are given in Table 4. We then fixed the size of the input data at 9 600 000 floating-point numbers and the number of nodes at 16, and varied the number of cores per node from 1 to 4. The results are given in Table 5. Table 4: Node-level scale-out (four cores per node, 2 560 000 floats). Number of procs Nodes

4 1

8 2

16 4

32 8

64 16

Speed-up Efficiency

1 1

1.999 0.999

3.974 0.994

7.560 0.945

13.815 0.863

Table 5: Core-level scale-out (16 nodes, 9 600 000 floats). Number of procs Cores per node

16 1

32 2

48 3

64 4

Speed-up Efficiency

1 1

1.965 0.983

2.884 0.961

3.852 0.963

Our measurements show that core-level scale-out is more efficient than node-level scale-out. The theoretical explanation is that node-level communication is more expensive than core-level communication. Figure 8 illustrates the two tables from the point of view of acceleration.

6

Conclusions

Scatter-gather parallel operations are old, well-understood concepts, and we do not pretend that SGL’s use of them is novel. What this paper has attempted to motivate and support is that BSP’s advantages for parallel software can be enhanced by the recursive, hierarchical and 17

Ideal Measured

Ideal Measured

4

Speed-up

Speed-up

15

10

2

5

0

0 0

5

10

0

15

1

2

3

4

5

Cores per node

Number of nodes (a) Node level (four cores per node)

(b) Core level (16 nodes)

Figure 8: Measured speed-up of SGL reduction: (a) node-level scale-out (Table 4); (b) core-level scale-out (Table 5). heterogeneous machine structure of SGL, while simplifying the programming interface even further by replacing point-to-point messages with logically centralised communications. From the perspective of programming research, SGL is a proposal to: 1. adapt BSML to a hierarchical machine structure; 2. remove its general communication primitive put (put is no longer a primitive but remains a possible optimised implementation); 3. replace mkpar with the scatter operation; and 4. replace proj with the gather operation. Our initial experiments with language definition, programming and performance measurement show that SGL combines a clean semantics, simplified programming of BSP-like algorithms and dependable performance measurement. One remaining open problem is the implicit treatment of the horizontal communication needed for operations like sample sort or bucket sort (Shi and Schaeffer, 1992). We are confident that the large body of knowledge on algorithms for cost-explicit models will yield many solutions to this problem. It is our opinion that SGL’s lesser expressive power with respect to message-passing structures is not only necessary for software reliability but also coherent with one of the most basic concepts in computing, namely recursive structures.

7

Future work

Ongoing work around SGL aims at developing: 1. an MPI/OpenMP implementation of a library for SGL’s parallel operations; 2. a compiler for the simple imperative SGL language described in this paper; 3. performance prediction for this compiler, based on our performance model; 4. optimisations based on the performance-prediction model and on the fundamental equation of modelling (Barker et al., 2009), Ttotal = Tcomp + Tcomm − Toverlap ; 5. a compiler from a domain-specific source application language (with no explicit parallel construct) to SGL; 6. horizontal child-to-child communications, as implicit semantics or as optimisations of SGL program executions. All of the above aspects of SGL’s development assume that it can be compiled and executed with a variable SGL-machine view, to more or less match the physical architecture. For example, a 18

network of bi-processors built from quad-core processors can have one, two or three levels when viewed as an SGL computer. At a more technical level, future work will investigate: 1. horizontal and vertical load balancing for heterogeneous machines; 2. pipelining or overlap behaviour, in the operational semantics or as optimisations; 3. SGL support for algorithms that use such horizontal communications; 4. including memory size in the model; 5. extended SGL implementations with accelerators (CUDA, Cell, SSE, AVX, etc.); 6. extended SGL implementations supporting fault tolerance.

Acknowledgements The first author thanks EXQIM S.A.S. for an Industrial Doctoral Scholarship under the French Government’s CIFRE scheme. The second author thanks W. F. McColl for introducing him to the BSP model in the early 1990s. SGL is inspired by the work of colleagues who are too numerous to cite here, but special thanks are due to Frédéric Loulergue and colleagues for their work on BSML. Both authors thank Frédéric Gava for useful comments on this paper, and EXQIM for access to the SGI hardware on which we conducted our experiments.

References Albert Alexandrov, Mihai F. Ionescu, Klaus E. Schauser, and Chris Scheiman. LogGP: Incorporating long messages into the LogP model – one step closer towards a realistic model for parallel computation. Technical report, University of California, Santa Barbara, Santa Barbara, CA, USA, 1995. George Almási, Ralph Bellofatto, José Brunheroto, Călin Caşcaval, José G. Castaños, Luis Ceze, Paul Crumley, C. Christopher Erway, Joseph Gagliano, Derek Lieber, Xavier Martorell, José E. Moreira, and Alda Sanomiya. An overview of the Blue Gene/L system software organization. In Euro-Par 2003 Parallel Processing, Lecture Notes in Computer Science, pages 543–555. Springer, 2003. Kevin J. Barker, Kei Davis, Adolfy Hoisie, Darren J. Kerbyson, Mike Lang, Scott Pakin, and José C. Sancho. Entering the petaflop era: The architecture and performance of Roadrunner. In Proceedings of the 2008 ACM/IEEE Conference on Supercomputing (SC’08), pages 1:1–1:11, Piscataway, NJ, USA, 2008. IEEE Press. Kevin J. Barker, Kei Davis, Adolfy Hoisie, Darren J. Kerbyson, Mike Lang, Scott Pakin, and José C. Sancho. Using performance modeling to design large-scale systems. Computer, 42(11): 42–49, 2009. Olaf Bonorden, Ben Juurlink, Ingo von Otte, and Ingo Rieping. The Paderborn University BSP (PUB) library. Parallel Computing, 29(2):187–207, 2003. José Luis Bosque and Luis Pastor. HLogGP: A new parallel computational model for heterogeneous clusters. In IEEE International Symposium on Cluster Computing and the Grid (CCGrid 2004), pages 403–410, 2004. WenGuang Chen, JiDong Zhai, Jin Zhang, and WeiMin Zheng. LogGPO: An accurate communication model for performance prediction of MPI programs. Science in China Series F: Information Sciences, 52:1785–1791, 2009. doi: 10.1007/s11432-009-0161-2. 19

David Culler, Richard Karp, David Patterson, Abhijit Sahay, Klaus Erik Schauser, Eunice Santos, Ramesh Subramonian, and Thorsten von Eicken. LogP: Towards a realistic model of parallel computation. SIGPLAN Notices, 28(7):1–12, 1993. Frank Dehne, Andreas Fabri, and Andrew Rau-Chaplin. Scalable parallel geometric algorithms for coarse grained multicomputers. In Proceedings of the Ninth Annual Symposium on Computational Geometry (SCG’93), pages 298–307, New York, NY, USA, 1993. ACM. Steven Fortune and James Wyllie. Parallelism in random access machines. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (STOC’78), pages 114–118, New York, NY, USA, 1978. ACM. Frédéric Gava and Frédéric Loulergue. A functional language for departmental metacomputing. Parallel Processing Letters, 15(3):289–304, 2005. Gaétan Hains. Subset synchronization in BSP computing. In H. R. Arabnia, editor, International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’98), volume I, pages 242–246, Las Vegas, NV, USA, 1998. David R. Helman, Joseph JáJá, and David A. Bader. A new deterministic parallel sorting algorithm with an experimental evaluation. ACM Journal of Experimental Algorithmics, 3, 1998. IBM Journal of Research and Development staff. Overview of the IBM Blue Gene/P project. IBM Journal of Research and Development, 52(1/2):199–220, 2008. Charles R. Johns and Daniel A. Brokenshire. Introduction to the Cell broadband engine architecture. IBM Journal of Research and Development, 51(5):503–519, 2007. James A. Kahle, Michael N. Day, H. Peter Hofstee, Charles R. Johns, Theodore R. Maeurer, and David J. Shippy. Introduction to the Cell multiprocessor. IBM Journal of Research and Development, 49(4.5):589–604, 2005. Rakesh Kumar, Dean M. Tullsen, Norman P. Jouppi, and Parthasarathy Ranganathan. Heterogeneous chip multiprocessors. Computer, 38(11):32–38, 2005. Charles E. Leiserson. Fat-trees: Universal networks for hardware-efficient supercomputing. IEEE Transactions on Computers, 34(10):892–901, 1985. Charles E. Leiserson, Zahi S. Abuhamdeh, David C. Douglas, Carl R. Feynman, Mahesh N. Ganmukhi, Jeffrey V. Hill, W. Daniel Hillis, Bradley C. Kuszmaul, Margaret A. St. Pierre, David S. Wells, Monica C. Wong, Shaw-Wen Yang, and Robert Zak. The network architecture of the Connection Machine CM-5 (extended abstract). In Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’92), pages 272–285, 1992. Chong Li and Gaétan Hains. A simple bridging model for high-performance computing. Technical Report TR-LACL-2010-12, Laboratoire d’Algorithmique, Complexité et Logique (LACL), Université Paris-Est Créteil, December 2010. Frédéric Loulergue. Conception de langages fonctionnels pour la programmation massivement parallèle. PhD thesis, Université d’Orléans, LIFO, Orléans, France, January 2000. Frédéric Loulergue. Bulk synchronous parallel ML. http://bsmllib.free.fr, 2010. Accessed 2011. Frédéric Loulergue, Gaétan Hains, and Christian Foisy. A calculus of functional BSP programs. Science of Computer Programming, 37(1–3):253–277, 2000. 20

W. F. McColl and David Walker. Theory and algorithms for parallel computation. In D. J. Pritchard and J. Reeve, editors, Euro-Par’98 Parallel Processing, volume 1470 of Lecture Notes in Computer Science, pages 863–864. Springer, 1998. Hanmao Shi and Jonathan Schaeffer. Parallel sorting by regular sampling. Journal of Parallel and Distributed Computing, 14(4):361–372, 1992. Angela C. Sodan, Jacob Machina, Arash Deshmeh, Kevin Macnaughton, and Bryan Esbaugh. Parallelism via multithreaded and multicore CPUs. Computer, 43(3):24–32, 2010. Alan Stewart. A programming model for BSP with partitioned synchronisation. Formal Aspects of Computing, 23(4):421–432, 2011. K. Ronald Sujithan. BSP parallel sorting by regular sampling – algorithm and implementation. Technical report, Computing Laboratory, University of Oxford, 1996. Leslie G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33 (8):103–111, 1990. Leslie G. Valiant. A bridging model for multi-core computing. Journal of Computer and System Sciences, 77(1):154–166, 2011. Glynn Winskel. The Formal Semantics of Programming Languages: An Introduction. MIT Press, Cambridge, MA, USA, 1993.

21

Related documents

• SGL: Towards a Bridging Model for Heterogeneous Hierarchical Platforms#1456818
• BuildBench: Benchmarking LLM Agents on Compiling Real-World Open-Source Software#1013446
• Adaptive Context Parallelism for Production LLM Serving#971443
• AI Prototyper: A Figma Plugin for Decomposition-Based GUI Prototyping with LLMs#373455
• PipeLive: Efficient Live In-place Pipeline Parallelism Reconfiguration for Dynamic LLM Serving#1063894