University of Tokyo
Akihiro Nomura, Yutaka Ishikawa

1 NBC = Non-blocking + Collective◦ Exploit communication – computation overlap◦ Do complicated communications easily and efficiently
 NBC will be introduced in upcoming MPI 3.0◦ In MPI 2.2, users have to implement collective routines
by hand to do non-blocking collectives.
 In HPL(High-performance Linpack),
6 implementations of non-blocking bcast are provided
 Existing implementation: LibNBC [Hoefler et al, 06-]

◦ Same APIs as MPI 3.0◦ POSIX pthread is used in the implementation2 Progression of collective communications◦ Collective communication consists of many pointto-point(P2P) (non-blocking) communications.
◦ P2P communications have data dependencies.
 E.g. send a data AFTER receiving them

◦ Progression resolves these dependencies and issues
all executable P2Ps as soon as possible.
 How to do progression in existing methods?

◦ Call progression explicitly (e.g. HPL’s Ibcasts)◦ Communication thread (e.g. LibNBC)

3



Call progression explicitly◦ HPL’s Ibcasts for example◦ MPI users have to callprogression routine inMPI library periodicallyby calling MPI_Test etc.
◦ If users don’t call progression,non-blocking collective
doesn’t progress.
◦ If users call progression
too frequently, CPU time
cost of needless MPI_Tests
becomes bigger.

init_for_collective();
while (1) {do_small_computation();do_progression();if (test_for_collective()) {do_rest_of_computation();break;}
if (no_work_left()) {wait_for_collective();
break;}}

4 Communication thread (e.g. LibNBC)◦ Creates a thread to perform progression◦ No explicit call required
Main Thread

NBC_Ibcast(…, &req);CreateThread

do_long_computation();
NBC_Wait(&req);

Context
Switchby OS

Communication Thread
while(in_progress) {do_progression();}5 Gap between MPI users and implementers◦ MPI user usually assumes all CPU cores can be used tocalculation
 User will create 1 process per core.

◦ Progression thread is required to implement nonblocking collectives

 In this situation…

◦ #threads exceeds #cores◦ Threads steals coreseach other Context switching cost Context switch timing
may not be optimal

Computing NodeCommunication(Progression)
ThreadContextSwitchMain(Calculation)
ThreadCoreCoreCoreCore6

 Progression Engine(PE)◦ Progression is implemented as kernel-mode
routines to avoid cost of using threads.
◦ PE is invoked by network interrupt handler◦ PE does not have user-mode contexts (memory etc)

Computing Node

Communication
Threads

Computing NodeComputingThreads

Context
SwitchInterrupt
CoreCoreCoreCoreCoreCoreCoreCore7

 KACC consists of 3 Layers◦ Algorithm Design◦ Progress Engine◦ P2P Routines

MPI Application
NBC Request
MPI Middleware Implemented onCommunication
ScheduleLinux Kernel 2.6

KACC

Algorithm Design API◦ As User-level library◦ As OS kernel module

Algorithm dataUserSpaceProgress EngineKernelSpaceMessage
RequestOpenIBTCPMX

P2P Layer

I/O Request

Kernel I/O Layer
Infiniband

Ethernet

Myrinet8

UserKernelCollective communications can be described as
DAG(Directed Acyclic Graph) [1, 2]◦ Nodes: Communications and Calculations◦ Edges: Dependencies



Make DAG structures on sharedmemory with kernel module.

◦ MakeSendNode(), ConnectNode()…
◦ To avoid passing executables tokernel directly (security issue)

Call Progress Engine
to execute/query algorithms◦ IssueCAD(), QueryCAD()◦ Communication with kernel module
is done by using shared memoryand system calls[1]: Hoefler et al, 2007[2]: MPIplans in MPI-Forum Wiki

STARTRecv

Recv

Calc+

Calc+
END

Example of MPI_Reduceon the root node9

UserKernel

 Process progression◦ = Issue P2P as soon as possible
 Issue communications by requests from otherlayers◦ From Algorithm Design: Start collectivecommunications (by system call)◦ From P2P Layer: Ready for communication /Complete communication (by Interrupt handler)

10UserKernelImplementation◦ Implemented using Linux tasklet◦ Does not have process context (VM address space) Drawback: all data have to be stuck to physical memory
before starting collective communication◦ Executed at the end of system calls and interrupt handlers◦ Requires Load balancing using IPI (Inter-processor Interrupt)
 Tasklet runs on the same CPU as its invoker (=interrupt)
 Network interrupts is concentrated on one specific core to send
packets efficiently
Core #0

INT

INT INT

Computation

Core #1

CommComm Computation
ReduceCore #2

Computation

Core #3

Computation

INT

INT INTComputation

Comm Computation
IPIReduceComputation
IPIComm
Computation

11

UserKernel Abstraction Layer for Progress Engine◦ Executes actual communication in non-blockingmanner◦ Runs on Linux tasklet context
 API like MPI’s non-blocking P2P (Isend/Irecv)◦ Completion is reported using callback routines
 Implemented non-blocking P2P on kernel-level TCP◦ TCP routine cannot sleep because tasklet doesn’t
have process context

12

We compared execution time and CPU usage offollowing implementations of non-blocking
broadcasts◦ KACC – Proposed Method◦ LibNBC – Using Thread for Progression◦ MPI – Calling Progression Explicitly and Periodically

CPU usage is calculated using following formula

EnvironmentAlgorithm◦ Usage[%] = (1 – Flops(Comm) / Flops(Idle)) x 100◦ Dual-core 2Ghz Opteron x 2 (4 core / node)◦ 8 node cluster, connected with 1Gbps Ethernet (Broadcom)◦ Linux kernel 2.6.18 (RedHat EL5)
◦ Pipeline broadcast on 32 MPI process Divide messages into small piece and send sequentially
#0#1

#2

#313

Execution Time Ratio

KACC is Better

1.210.80.6

KACC / LibNBC

0.4

KACC / MPI
0.2

0
1E+02

1E+03

1E+04

1E+05

1E+06

1E+07

1E+08

Message Size [Bytes]

KACC is faster than existing methods
 If message size is small, KACC slows down due to overheads14CPU time loss ratio [%]Better100
9080
7060504030
20
100
1E+02

KACC
LibNBC
MPI

1E+03

1E+04

1E+05

1E+06

1E+07

1E+08

Message Size [Bytes]
KACC consumes less CPU time in the same algorithm

15CPU time loss ratio [%]Better1009080706050403020100
1E+02

KACC
LibNBC
MPI

1E+03

1E+04

1E+05

1E+06

1E+07

1E+08

Message Size [Bytes]

If user calls Test/Progression more frequently, most of CPU timeis spent on communication under the existing methods.
 On KACC, CPU time consumption ratio is still small.
16 We have proposed KACC facility◦ A new method to implement non-blocking collectivecommunications◦ Use kernel’s interrupt context to avoid context switchingcosts of threads

 We evaluated KACC

◦ KACC is 21% faster than LibNBC◦ KACC consumes at least 33% less CPU time than LibNBC

 Future work

◦ Provide a way to do user-defined operations.
 Application’s signal handler?

VM code w/ verification?

◦ Provide other P2P layers than TCP◦ Improve performance17Thank you

18