A Framework for Optimizing Interprocessor Communication

Filippo Gioachin

Sameer Kumar

Outline

Motivation

Optimization pattern:

Collective communication

Case study 1: All-to-all multicast

Case study 2: One-to-all multicast

The learning framework

Why studying communication?

Critical for parallel program applications

Communication

exchange

Compute phase 1

Compute phase 2

using data exchanged

Virtual processor

Minimizing processor usage

i.e. using co-processor

charm can use the overhead
transferred to the co-processor
to do useful work

AAM – All-to-All Multicast
Who uses them?

Cosmology

Namd

CPAIMD

In general, whenever a global exchange of information has to be performed

Equivalent to MPI_AllGather

Model

Tp2p = α + mβ

α is the total software overhead of sending the message

β is the per byte network overhead

m is the size of the message

Short messages: α dominates

Large messages: β dominates

Algorithms for multicast: MESH

Multicast inside a row

Multicast inside a
column all the messages
received in phase 1

γ is the cost of message combining

Algorithms for multicast: GRID

Multicast over y

Multicast over x

Multicast over z

Algorithms for mcast: HYPERCUBE

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

15

m

α+βm

Time

Msg size

2m

4m

8m

α+8βm

α+4βm

α+2βm

Quadrix Elan (1)

Special purpose memory in the NIC

Copy to elan network memory and send it faster

Pros

Higher bandwidth

610MB/s against 250 (bidirectional)

βem=3.28, β=8 ns/byte

Less processor overhead

Cons

overhead copying data to NIC memory

δ is the per byte cost to copy data to elan memory

Copy to elan memory and from there send to all processors

βem is the per byte overhead sending from elan memory

δ is the per byte cost to copy data to elan memory

Why?

PCI contention on the main memory bus

Quadrix Elan (2)

The same message is sent more than once

Good for mesh and grid

Small increase in number of messages sent

We send large messages in last steps and we can use βem

Not for hypercube (different message every step)

Hybrid solution where we switch to direct sending last k steps

k

Algorithms for mcast: HYPERCUBE

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

15

m

α+βm

Time

Msg size

2m

α+(β+γ)2m

α+(β+γ)8m

α+(β+γ)4m

4δm+3(α+4βemm)

Performance on 256 nodes

Performance sending from Elan memory

CPU vs. Completion time

Direct Strategies

Processors send directly their message to others,
without using message combining

Useful for large messages where γ and δ become important

Problem:

we don't want to have stalls due to congestion of the network

find contention free patterns to use

Fat-tree Network (1)

Popular network topology for clusters (Quadrix uses it)

Bisection bandwidth O(P)

Network scales to several thousands of nodes

Topology: k-ary, n-tree (known also as Butterfly)

a)

4-ary 1-tree

b)

4-ary 2-tree

4-ary tree

Fat-tree Network (2)

c)

4-ary 3 tree

True for off-line

Not always for on-line

Every processor sends one message and receives one

permutations

All permutations are contention free

Prefix permutation

0

1

2

3

4

5

6

7

p XOR 1

0

1

2

3

4

5

6

7

p XOR 4

0

1

2

3

4

5

6

7

p XOR 3

0

1

2

3

4

5

6

7

p XOR 2

Prefix permutation k

Processor i sends data to

k = 4 to 7

k = 8 to 11

Cyclic shift permutation

Cyclic shift by k

Processor i sends a message to

Contention free if

0

1

2

3

Shift by 2

0

1

2

3

Shift by 1

0

1

2

3

Shift by 3

j=3

j=0

j=2

j=1

Strategy: Ring

Performs all to all multicast by sending messages along a ring formed by the processors

Equivalent to P-1 cyclic-shift-by-1 operations

Drawback

Processors send different messages in each step

0

1

2

i

i+1

P-1

……

……..

Strategy: Prefix Send

P-1 prefix permutations

In stage j, processor i sends a message to processor

Can send messages from Elan memory

Bad performance on large fat-trees

Sends P/2 messages to far-away nodes at distance P/2 or more away

Wire/Switch delays restrict performance

Strategy: k-Prefix

Hybrid of ring strategy and prefix send

Prefix send used in partitions of size k

Ring used across partitions

0

1

2

i

i+1

P-1

……

……..

Ring across fat-trees of size k

Prefix Send within

Performance

Performance

One-to-All (Multicast)

Issue:

Only one processor busy sending data

(P-1)m bytes need to be delivered

want to reduce the time

Asymmetric

Increase bandwidth

Hypercube

Hypercube strategy

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

15

Waiting for previous send to finish and then starting to send to next processor in list

Delay for resending

Try to start cascaded
sends earlier

Problem:

sending large messages
takes time, and far-away
processor get delayed

Message splitting and pipelining

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

15

Same delay for resending

Waiting for previous send to finish and then starting to send to next processor in list, smaller than before since messages are shorter

Split the message in

multiple chunks, and

send them in a

pipelined fashion

Pro:

far-away nodes will

receive the data earlier

Cons:

the overhead to send

in processor 0 will

increase due to α

Adaptive Learning

Different strategies win in different contexts

Communication patterns of applications can be learned

Record the messages exchanged by the objects

Choose the best strategy at runtime

Different strategies available

Small messages vs. Large messages

Few processors vs. Many processors

Different network topologies

minimize Completion time vs. CPU time

Summary

Motivation

Optimization collective communication

All-to-all multicast

Message combining for short messages

Direct contention free sending for large messages

One-to-all multicast

Message pipelining

The learning framework

2004-10-12T22:39:46