Aleksandr Drozd, Naoya Maruyama, Satoshi Matsuoka A(TITECH)
Multi GPU ReadIn mosttheir demolecul
DNA ccalled nThe fouA), cyt

100,000	  Times	  Fold	  EBD	  “Convergent”	  System	  Overview	

Problem Domain

Tasks	  5-­‐1~5-­‐3	

EBD	  ApplicaQon	  Co-­‐Design	  and	  ValidaQon	  Problem Domain
Large	  Scale	  Genomic	  CorrelaQon	

Task	  3	EBD	  Programming	  System	  Task6	 EBD	  Performance	  Modeling	  	  &	  EvaluaQon	
Introduction

Large	  Scale	  Graphs	  and	  Social	  Infrastructure	  Apps	

Data	  AssimilaQon	  in	  Large	  Scale	  Sensors	  and	  Exascale	  Atmospherics	

Task	  	To 4decipher
the information co“converged”	  Real-­‐Time	  weEBD	  needto determine
the order
Resource	  Scheduling	  This task is important for many
Task	  2	EBD	  Distrbuted	  Object	  Store	  ofon	  science and medicine.
areas
Cartesian	  Plane	
100,000	  NVM	  Extreme	  Compute	  Modern sequencing techniques
and	  Data	  Nodes	  molecule
Ultra	  Parallel	  &	  Low	  Powe	  I/O	  EBD	  into pieces (called rea
processed separately EBD	  to Kincrease“Convergent”	  Supercomputer	  VS	  Task	  1	~10TB/s⇒~100TB/s⇒~10PB/s	sequencing throughput.
日本地図

EBD	  Bag	

13/06/06 22:36

KVS	

KVS	Graph	  Store	

KVS	

1000kmUltra	  High	  BW	  &	  Low	  Latency	  NVM	TSUBAME	  2.0/2.5	

TSUBAME	  3.0	Ultra	  High	  Bmust
W	  &	  Low	  NW	  	to the r
Reads
beLatency	  aligned
file:///Users/shirahata/Pictures/日本地図.svg

1/1 ページ

sequence to determine
their po3D	  stacking	molecule. This process is called

Processor-­‐in-­‐memory	Aleksandr Drozd, Naoya Maruyama, Satoshi Matsuoka A(TITECH)
Multi GPU ReadIn mosttheir demolecul
DNA ccalled nThe fouA), cyt

Problem Domain

100,000	  Times	  Fold	  EBD	  “Convergent”	  System	  Overview	
Large	  Scale	  Genomic	  CorrelaQon	

Large	  Scale	  Graphs	  and	  Social	  Introduction
Infrastructure	  Apps	

Problem
DomainPGAS/ScripIng	  MPI	

Languages	  for	  EBD	  	Data	  AssimilaQon	  in	  Large	  Scale	  Sensors	  and	  Exascale	  Atmospherics	

MapReduce	

Workﬂow	

ToAlgorithm	  decipher
the	   information co
Kernels	  (Sort,	  Mweatching,	  Graph	  ,	  etc.)	  	the orderneedtoTraversals,	  determineThis task
importantfor many
Abstract	  Data	  isModels	  	  System	  (Array,	  Key	  Value,	  Sperce	  ofData	  Model,	  Tree,	  Graph,	  etc.)	
areas
scienceandmedicine.
Hardware	  Cartesian	  Plane	
EBD	  Bag	Sojware	  Design	  	Modern sequencing techniques
Library	Network	  	molecule into pieces (called reaGraph	  Store	
processed separately EBD	  to Kincrease
VS	  I/O	  for	  NVM/	  HPC	  File	  System/	  Object	  Storage	  	sequencing throughput.
Reads
beLatency	  aligned
Ultra	  High	  BW	  &	  Low	  Latency	  NVM	Ultra	  High	  Bmust
W	  &	  Low	  NW	  	to the rsequence to determine their po
TSUBAME	  2.0/2.5	 TSUBAME	  3.0	 Processor-­‐in-­‐memory	 3D	  stacking	molecule. This process is called日本地図

13/06/06 22:36

KVS	

KVS	

KVS	

1000kmfile:///Users/shirahata/Pictures/日本地図.svg

1/1 ページ

Hamar	  (Highly	  Accelerated	  Map	  Reduce)	  [Shirahata,	  Sato	  et	  al.	  Cluster2014]	
• A	  	  soqware	  framework	  for	  large-­‐scale	  supercomputers	  	  w/	  many-­‐core	  accelerators	  and	  local	  NVM	  devices	  – AbstracQon	  for	  deepening	  memory	  hierarchy	  • Device	  memory	  on	  GPUs,	  DRAM,	  Flash	  devices,	  etc.	  	  • Features	  – Object-­‐oriented	  	  • C++-­‐based	  implementaQon	  • Easy	  adaptaQon	  to	  modern	  commodity	  	  many-­‐core	  accelerator/Flash	  devices	  w/	  SDKs	  – CUDA,	  OpenNVM,	  etc.	  

– Weak-­‐scaling	  over	  1000	  GPUs	  	  • TSUBAME2	  – Out-­‐of-­‐core	  GPU	  data	  management	  • OpQmized	  data	  streaming	  between	  	  device/host	  memory	  • GPU-­‐based	  external	  sorQng	  – OpQmized	  data	  formats	  for	  	  many-­‐core	  accelerators	  • Similar	  to	  JDS	  format	  Hamar	  Overview	
Rank	  0	Rank	  1	Shuﬄe	

Shuﬄe	Shuﬄe	

Map	

Rank	  n	

Reduce	Reduce	Shuﬄe	

Map	

Local	  Array	

Reduce	Map	

Local	  Array	

Local	  Array	

Local	  Array	

Data	  Transfer	  between	  ranks	
Local	  Array	

Local	  Array	

Local	  Array	

Local	  Array	

Distributed	  Array	
Local	  Array	  on	  NVM	Device(GPU)	  Data	

Local	  Array	  on	  NVM	Host(CPU)	  Data	

Data	  Object	
Local	  Array	  on	  NVM	
Virtualized	  Local	  Array	  on	  NVM	Memcpy	  	  (H2D,	  D2H)	

ApplicaQon	  Example	  :	  GIM-­‐V	  Generalized	  IteraQve	  Matrix-­‐Vector	  mulQplicaQon*1	
• Easy	  descripQon	  of	  various	  graph	  algorithms	  by	  implemenQng	  combine2,	  combineAll,	  assign	  funcQons	  • PageRank,	  Random	  Walk	  Restart,	  Connected	  Component	  – v’	  =	  M	  ×G	  v	  	  where	  v’i	  =	  assign(vj	  ,	  combineAllj	  ({xj	  |	  j	  =	  1..n,	  xj	  =	  combine2(mi,j,	  vj)}))	  	  (i	  =	  1..n)	  – IteraQve	  2	  phases	  MapReduce	  operaQons	  Straighyorward	  implementaQon	  using	  Hamar	v’	v’i	＝	v	M	assign	mi,j	×G	vj	

combine2	  (stage1)	combineAll	  and	  assign	  (stage2)	

*1	  :	  Kang,	  U.	  et	  al,	  “PEGASUS:	  A	  Peta-­‐Scale	  Graph	  Mining	  System-­‐	  ImplementaQon	  	  and	  ObservaQons”,	  IEEE	  INTERNATIONAL	  CONFERENCE	  ON	  DATA	  MINING	  2009	

MapReduce-­‐based	  Graph	  Processing	  with	  Out-­‐of-­‐core	  Support	  on	  GPUs	
• Hierarchical	  memory	  management	  for	  large-­‐scale	  	  graph	  processing	  using	  mulQ-­‐GPUs	  – Support	  out-­‐of-­‐core	  processing	  on	  GPU	  – Overlapping	  computaQon	  and	  CPU-­‐GPU	  communicaQon	  Performance	  [MEdges/sec]	

Bemer	• PageRank	  applicaQon	  on	  TSUBAME	  2.5	   2.81	  GE/s	  on	  	  3072	  GPUs	  	  (SCALE	  34)	Weak	  scaling	  performance	

3000	  1CPU	  (S23	  per	  node)	  1GPU	  (S23	  per	  node)	  2CPUs	  (S24	  per	  node)	  2GPUs	  (S24	  per	  node)	  3GPUs	  (S24	  per	  node)	  2500	  2000	  1500	  2.10x	  Speedup	  (3	  GPU	  v	  2CPU)	

1000	  500	  0	  0	  200	  400	  600	  800	  Number	  of	  Compute	  Nodes	

1000	  1200	  reliable storage designs for resilient extreme scale computing.

GPUアクセラレータと不揮発性メモリを考慮した
3.2 Burst Buﬀer System
Sato et al. HPC141]
To solve the problems I/O構成法
in a flat buﬀer system, we[Shirahata,
consider aburst buﬀer system [21]. A burst buﬀer is a storage space tobridge the gap in latency and bandwidth between node-local stor- 	  age 16	  and the枚PFS,のand ismSATA	  shared by a subsetof computenodes.
SSD	  を用いたプロトタイプマシンの設計	  Although additional nodes are required, a burst buﬀer can oﬀer
量:advantages	  256GB	  includingx	  16枚	  →	  reliability Readバンド幅:	  0.5GB/s	  	  x	  16枚	  →	  a system容
manyhigherandeﬃciency over a flat buﬀer system. A burst buﬀer system is morereliable for checkpointing because burst buﬀers are located ona smaller number of dedicated I/O nodes, so the probability oflost checkpoints is decreased. In addition, even if a large numberof compute nodes fail concurrently, an application can still access the checkpoints from the burst buﬀer. A burst buﬀer systemprovides more eﬃcient utilization of storage resources for partial
restart of uncoordinated checkpointing because processes involving restart can exploit higher storage bandwidth. For example, if
compute node 1 and 3 are in the same cluster, and both restartA	  single	  mSATA	  SSD	  8	  integrated	  mSATA	  SSDs	  from a failure, the processes can utilize all SSD bandwidth unlike
a flat buﬀer system. This capability accelerates the partial restartof uncoordinated checkpoint/restart.	  	  	  	  4TB	  	  	  Table 1CPUMemory
M/BSSDSATA converter
RAID Card8	  GB/s	  Node specification

Intel Core i7-3770K CPU (3.50GHz x 4 cores)
Cetus DDR3-1600 (16GB)
GIGABYTE GA-Z77X-UD5H
Crucial m4 msata 256GB CT256M4SSD3(Peak read: 500MB/s, Peak write: 260MB/s)
KOUTECH IO-ASS110 mSATA to 2.5’ SATA
Device Converter with Metal Fram
Adaptec RAID 7805Q ASR-7805Q Single

RAID	  cards	  Prototype/Test	  machine	  複数 mSATA	  SSD	  の	  I/O	  性能	  〜	  7.39	  GB/s	  (RAID0	  を使用)	  GPU	  への	  I/O	  性能	  〜	  3.06	  GB/s	  (PCI-­‐E	  上限)	  FIO	  による複数 mSATA	  SSD	  の	  I/O	  性能	

行列ベクトル積による	  GPU	  への	  I/O	  性能	

9000	  8000	  7000	  6000	  5000	  4000	  3000	  2000	  1000	  0	  Raw	  mSATA	  4KB	  RAID0	  1MB	  RAID0	  64KB	  0	  5	  10	  #	  mSATAs	15	  3.5	  Throughuput	  [GB/s]	

Bandwidth	  [MB/s]	

GPUから複数 mSATA SSD への
I/O性能の予備評価

3	  2.5	  2	  1.5	  1	  0.5	  0	  Raw	  8	  mSATA	  8	  mSATA	  RAID0	  (1MB)	  8	  mSATA	  RAID0	  (64KB)	  20	  Matrix	  Size	  [GB]	

[Shamoto, Sato et al.
BigData 2014]

Sorting for EBD

Plugging in GPUs for large-scale sorting
HykSort 1threadHykSort 6threads
HykSort GPU + 6threads

Keys/second(billions)30

20

GPU implementation ofsplitter-based sorting (HykSort)•

Weak scaling performance (GrandChallenge on TSUBAME2.5)

x1.4

0.25
[TB/s]

x3.61––•

100•

HykSort 6threads
HykSort GPU + 6threads
PCIe_10
PCIe_100
PCIe_200
PCIe_501000
0500
1500
2000
Predictionof our implementation# of proccesses(2 proccessesper node)
K20x

1 ~ 1024 nodes (2 ~ 2048 GPUs)
2 processes per node and each node has
2GB 64bit integer

Yahoo/Hadoop Terasort: 0.02[TB/s]–Including I/Ox389• Performance prediction

x4 faster than K20x}

Keys/second(billions)60

PCIe_#: #GB/s bandwidthof interconnect between
CPU and GPU

40

2000500

1000 1500 2000 0500

1000 1500 2000

# of proccesses (2 proccesses per node)x2.2 speedup comparedto CPU-based
implmentataion when the# of PCI bandwidth
increase to 50GB/s

8.8% reduction ofoverall runtime when
the accelerators work 4times faster than K20x

Large	  Scale	  Graph	  Processing	  Using	  NVM	  [Iwabuchi	  Sato	  et	  al.	  BigData2014]	
1.	  Hybrid-­‐BFS	  (	  Beamer’11	  )	   2.	  Proposal	  	Source	  Top-­‐down	  DRAM	

NVM	

Holds	  highly	  accessed	  data	

Holds	  full	  size	  of	  Graph	

Bomom-­‐up	  CPU	DRAMIntel Xeon E5-2690 × 2	NVM	EBD-I/O 2TB × 2	256 GB	

www.crucial.com/	

mSATA
mSATA
・・・	  SSD	SSD	×	  8	   mSATA-SSD

RAID Card (RAID 0)	
www.adaptec.com	

RAID
Card

Median	 GigaTEPS	 3.	  Experiment	  (Giga	 Traversed	 Edges	 Per	 Seconds)	 

Load	  highly	  accessed	  graph	  data	  before	  BFS	6.0	 	 

Limit	 of	 DRAM	 Only	 
4.1	 

5.0	 	 4.0	 	 3.0	 	 2.0	 	 1.0	 	 0.0	 	 DRAM	 +	 EBD-I/O	 
DRAM	 Only	 

3.8	 

4	  Qmes	  larger	  graph	  with	  6.9	  %	  of	  degradaQon	  23	 24	  25	 26	  27	 28	  29	 30	  31	 
SCALE	 
(#	 vertices	 =	 2SCALE)	 

Results	  :	  BFS	  Performance	  The	  Graph	  500	  2014	  June	  	  	  	  	  	  	  	  	  	  	  DRAM	  +	  NVM	  model	MEM-­‐CREST	  Node	  #2	  EBD-­‐RH5885v2	  GraphCrest	  Node	  #1	  	(Huawei	  Tecal	  RH5885	  V2)	  (Supermicro	  2027GR-­‐TRF)	  	DRAM	
NVM	

128	  GB	

256	  GB	

ioDrive2	  1.2	  TB	  ×	  2	 EBD-­‐I/O	  2TB	  ×	  2	1024	  GB	•
•Tecal	  ES3000	  800GBx2,1.2TBx2	  EBD-­‐I/O	  4TB	  ×	  2	SCALE	  30	  (500GB)	

31	  (1TB)	

33	  (4TB)	

GTEPS	

7.98	

13.80	  	3.11	

MTEPS	  /	  W	28.88	  	35.21	

3.42	

(Total	  Data	  Size)	

The	  2nd	  Green	  Graph500	  list	  on	  Nov.	  2013	
• Measures	  power-­‐eﬃcient	  using	  TEPS/W	  raQo	  • Results	  on	  various	  system	  such	  as	  Huawei’s	  RH5885v2	  w/	  Tecal	  ES3000	  PCIe	  SSD	  800GB	  *	  2	  and	  1.2TB	  *	  2	  • hmp://green.graph500.org	  Expectations for Next-Gen Storage System(Towards TSUBAME3.0) 	
• Achieving high IOPS

– Many apps with massive small I/O ops• graph, etc.

• Utilizing NVM devices– Discrete local SSDs on TSUBAME2– How to aggregate them?

• Stability/Reliability as Archival Storage	
• I/O resource reduction/consolidation– Can we allow a large number of OSSs forachieving ~TB/s throughput– Many constraints• Space, Power, Budget, etc.

Current Status 	
• New Approaches••

Tsubame 2.0 has pioneered the use of local flash storage asa high-IOPS alternative to an external PFSTired and hybrid storage environments, combining (node)local flash with an external PFS• Industry Status• High-performance, high-capacity flash (and other newsemiconductor devices) are becoming available
at reasonable cost
• New approaches/interface to use high-performance devices(e.g. NVMexpress)30