System Software Research (1)Towards Next-Generation Supercomputing

Performance Analysis and Runtimes
Performance Metrics and Tools

Task Parallel Runtimes

We’ve installed following performance monitoring
tools into TSUBAME2.5 and can get performancedata of real applications in following metrics.

Support for many types of control makes them a popular choice

Tool
TypeMetrics
Scalasca Profiler Time, Visit, MPI Communication, PAPI
VampirTracer Time, MPI Comm., GPU Comm., PAPI
Exana
TracerTracerMemory Access (Instruction Level)
Exana
PAPI
PAPI
LibraryLibrary
Instruction Mix, Main Memory Access

Runtime Layer(Cilk, TBB, OpenMP, etc)

Regular Parallelism
Divide and Conquer

Irregular Parallelism

Common issues in runtime scalability:
1. Runtime System overheads

Performance Repository Schema

Cores

2. Scheduling Constraints

3. Resource contention

Causes parallel idleness (PI)

Causes parallelization overhead (PO)We’re giving seminar for those performance tools
for TSUBAME users.

Causes Work Time Inflation (WTI)

Case Study: scalability of recursive MatMul
LIFO local
scheduling

CCCCC

LIFO local
scheduling

Task Queues

FIFO workstealing

MassiveThreads

CCToolName, Version
Supported Metrics

1.7Work First“shepherd”

MassiveThreads
Threading Building Blocks
QThread1.6Speed-Up

QThread

121.2

0.9
0.85

0.825

1.1

4

0.95

0.875

1.38

10.925

1.4

0.8

0.775

1 24612
Number of Cores

1824

Speed-UP

This is collaborative work with Future Technologies Group, Oak Ridge National Laboratory.

bulk FIFO
work stealing

0.975

Non-Work Overheads

160NUMA
node #24-socket Intel Xeon E7-4807 (1.86GHz). Matrix size 4096 elem (64MB)

MassiveThreads Speed-Up
Threading Building Blocks Speed-Up
QThread Speed-Up
20

Proposed Design ofApplication Schema

Tool Result
Selected Metrics, Tool
Link to Raw Data from Tools

C(shepherd)

Thread Building Blocks

24

Summary Metrics
Metric, Result(Common form throughout tools)

C

LIFO global
scheduling

1.5

Platform#Nodes, #CPUs, #GPUs, NetworkC

2

Experiment Details:

Experiment
Platform, Library selection,
Runtime Options, Problem size

C

Task Queues

FIFO work
stealing

Work FirstC

Normalized Speed-Up x Overhead ProductWe’re building application performance repository toknow following things through performance analysis.
• Which machine can solve my application well?
• Which application are suitable for our supercomputer?
We collect various performance data from manysupercomputers and correlate them to answer thesequestions.
Application
Name, Version, Field, License,
Library Requirement

Tasks

1.0

1 24612
Number of cores

18240.75

Overhead (PI x PO)

MassiveThreads Speed-Up x OVR
Threading Building Blocks Speed-Up x OVR
QThread Speed-Up x OVR
1 2 4 61218
Number of Cores

24Speed-Up x OVR
Product (1/WTI)

Data Access Trace
CORE #2@in1101112@in3

9CORECORE#1L18#1L1L2!

17

Reuse Ratio (%)

542 3

42 3

MAIN MEMORY

40

1

10FINB
M
32B

M
16B

8M

B

4M

B

(Data Window (KB)

-Reuse Ratio (%)

Reuse Ratio (%)

80

70
60
50
40
30
20
10

F
IN B
8M
12B
M
64
B
M
32
B
M
16B
8M
B
4M
B
2M
B
1M B
2K
51 B
6K
25 B

128K

KB

64

Data Window

KB

32

KB

16

B

B

8K

0

MassiveThreads
Threading Building Blocks
QThreadData Window

Correlation of KRD with Hardware Metrics

1) Complex inter-task dependencies2) Heterogeneous task runtimes3) Input dependent control flow4) Mix of compute/memory bound tasks+Where and when to schedule each task
on a CPU/GPU system?

1) All-GPU: All tasks on GPU
2) Simple Hybrid, P2P on GPU
and remaining phases on CPU
3) Optimal scheduling, basedon design space exploration

2 NUMA node / 12 cores

100

RuntimeLibrary98
Reuse Ratio (%)

)

40

4K

F
IN B
8M
12B
M
64
B
M
32
B
M
16B
8M
B
4M
B
2M
B

1M

B

B

2K

51

6K

B

8K

25

12KB

64

KB

32

KB

16

B

8K

0!

Comparison of StarPU with:

60

20

MassiveThreads
Threading Building Blocks
QThreadCase Study: Fast Multipole Method

Approach:
Use dynamic task scheduler

9080&

*

4 NUMA nodes / 24 cores100)

60

2M(&'($)

20,%

10 11 12generation

B
1M
B
2K51
B
6K
25
B
8K
12($80B
0K

100

C
ORE 5 6 7 8 94
#2 histogram

665

LLC

Correlation of KRD with Schedulers
1 NUMA node / 6 cores

2 3100Trace format@out2"#
Synchronized/Merged Trace

CORE
#2

Heterogeneous Scheduling@out1

KERNEL

7L2@in2

9- Reuse distance of Kernel data accesses- Coarse Grain to reduce overheads- Tool for the analysis of LLC performanceand its correlation with the WTI

8Kernel Reuse Distance!

KRD metric

Data Access Trace
CORE #1

101112

Data Reuse and Heterogeneity

1.653 sec

2.091x10 6

17479 ns (1.0274x)

TBB

1.721 sec

2.663x10617885 ns (1.0513x)

QThread2.564 sec

10.866x10 6

MTH

96
94

Exec Time LLC Misses Kernel Time & WTI

19804 ns (1.164x)

92
90

MassiveThreads Reuse DistanceThreading Building Blocks Reuse Distance
QThread Reuse Distance

888MFIN

12BB

B

M
64M
32B

B

M

168M

B4M

B2M

Global LIFO increases locality in single socket
MTH and TBB work stealing across node more efficient
Qthread performance on multiple sockets is hampered
by runtime overheads. WTI also increases as a result

Lessons learned:- Task Size Matters:
CPUs prefer fine-grained tasks
GPUs prefer coarse-grained tasks- Communication / disjoint memories- Task runtime prediciton in irregularapplications is a complex problem

Data Window (KB)

http://www.gsic.titech.ac.jp/sc13