Automatic Cache and Local Memory
Optimization for Multicores
Hironori Kasahara
Professor, Dept. of Computer Science & Engineering
Director, Advanced Multicore Processor Research Institute

Waseda University, Tokyo, JapanIEEE Computer Society
President Elect 2017, President 2018
URL: http://www.kasahara.cs.waseda.ac.jp/
Waseda Univ. GCSC

2

Past IEEE Computer Society Presidents

Chairs of the IRE ProfessionalGroupon Electronic Computers
1951-53 Morton M. Astrahan
1953-54 John H. Howard
1954-55 Harry Larson
1955-56 Jean H. Felker
1956-57 Jerre D. Noe
1957-58 Werner Buchholz
1958-59 Willis H. Ware
1959-60 Richard O. Endres
1960-62 Arnold A. Cohen1962-64 Walter L. Anderson

Chairs & Presidents of the IEEE
Computer Society
1996 Mario R. Barbacci
1964-65 Keith Uncapher
1997 Barry W. Johnson
1965-66 Richard I. Tanaka
1998 Doris L. Carver
1966-67 Samuel Levine
1999 Leonard L. Tripp
1968-69 Charles L. Hobbs
2000 Guylaine M. Pollock
1970-71 Edward J. McCluskey 2001 Benjamin W. Wah
1972-73 Albert S. Hoagland
2002 Willis K. King
1974-75 Stephen S. Yau
2003 Stephen Diamond
1976
Dick B. Simmons2004 Carl K. Chang
1977-78 Merlin G. Smith
2005 Gerald L. Engel
1979-80 Tse-Yun Feng
2006 Deborah M. Cooper
1981
Richard E. Merwin 2007 Michael R. Williams1982-83 Oscar N. Garcia
2008 Rangachar Kasturi
Chairs of the AIEE Committee
1984-85 Martha Sloan
2009 Susan K. (Kathy) Land,on Large-Scale Computing Devices
1986-87 Roy L. Russo
2010 James D. Isaak
1946-49 Charles Concordia
1988 Edward A. Parrish
2011 Sorel Reisman
1949-51 John Grist Brainerd
1989 Kenneth A. Anderson
2012 John W. Walz
1951-53 Walter H. MacWilliams
1990 Helen M. Wood2013 David Alan Grier
1953-55 Frank J. Maginniss
1991 Duncan H. Lawrie
2014 Dejan S. Milojicic
1955-57 Edwin L. Harder1992 Bruce D. Shriver
2015 Thomas M. Conte
1957-59 Morris Rubinoff
1993 James H. Aylor2016 Roger U. Fujii
1959-61 Ruben A. Imm
1994 Laurel V. Kaleda
2017 Jean-Luc Gaudiot
1961-63 Claude A. Kagan
1995 Ronald G. Hoelzeman
2018 Hironori Kasahara
1963-64 Gerhard L. Hollander

IEEE Computer Society BoG(Board of Governors) Feb.1, 2017

Toward 2018
1.

Refining content and services to further improve the satisfaction ofCS members;

2.

Considering an incentive for volunteers to further accelerate CS
activities and promptly provide technical benefits for people
around the globe;

3.

Offering more attractive services for practitioners in industry;

4.

Providing the world’s best educational content and historicaltreasures for future generations, which only the CS can create
with our pioneering researchers (for example, the Multicore
Compiler Video Series found atwww.computer.org/web/education/multicore-video-series);

5.

Thinking about sustainable membership fees while considering thediversity of economic situations within the 10 regions;6.

Cooperating with other IEEE societies and sister societies in atimely and efficient manner;

7.

Intelligibly introducing the latest computer-related technologies toyounger generations, including children, so that they can realize
their technological dreams.
5Multicores for Performance and Low PowerPower ∝ Frequency * Voltage2

ILRAM I$

Core#0URAMDLRAM D$Core#2

Core#1
SNC0LBSC

Power consumption is one of the biggest problems for performancescaling from smartphones to cloud servers and supercomputers(“K” more than 10MW) .
(Voltage ∝ Frequency)

Power ∝ Frequency3
Core#3

If Frequency is reduced to 1/4
VSWC(Ex. 4GHz1GHz),
Core#6
Core#7
Power is reduced to 1/64 andCore#4
Core#5
Performance falls down to 1/4 .
<Multicores>
DDRPADIEEE ISSCC08: Paper No. 4.5,
If 8cores are integrated on a chip,M.ITO, … and H. Kasahara,“An 8640 MIPS SoC with
Power is still 1/8 andIndependent Power-off Control of 8CPUs and 8 RAMs by an AutomaticPerformance becomes 2 times.
Parallelizing Compiler”
DBSC

CSM

SNC1SHWYGCPG

6

Earthquake Simulation“GMS” on Fujitsu M9000
Sparc CC-NUMA ServerWith 128 cores, OSCAR compiler gave us 100 times
speedup against 1 core execution and 211 times speedup
against 1 core using Sun (Oracle) Studio compiler.

7OSCAR Parallelizing Compiler
To improve effective performance, cost-performanceand software productivity and reduce powerMultigrain Parallelizationcoarse-grain parallelism among loops
and subroutines, near fine grain
parallelism among statements inaddition to loop parallelism

1

Data Localization
Automatic data management for
distributed shared memory, cacheand local memory

Data Transfer Overlapping
Data transfer overlapping using Data
Transfer Controllers (DMAs)

Power Reduction
Reduction of consumed power bycompiler control DVFS and Powergating with hardware supports.

1824

32

54

10

11

96

12

7

14

13

15

17

19

25

16

21

22

23

20

26

dlg2

dlg1

dlg3

dlg0

28

29

Data Localization Group27

831333230

Generation of Coarse Grain Tasks
Ｍacro-tasks (MTs) Block of Pseudo Assignments (BPA): Basic Block (BB) Repetition Block (RB) : natural loop Subroutine Block (SB): subroutine

Program

BPA

Near fine grain parallelization

RB

Loop level parallelization
Near fine grain of loop body
Coarse grain
parallelization

SB

Total
System

1st. Layer

Coarse grain
parallelization
2nd. Layer

9

BPA
RB
SB
BPA
RB
SB

BPA
RB
SB
BPA
RB
SB
BPA
RB
SB
BPA
RB
SB

3rd. Layer

Earliest Executable Condition Analysis for Coarse
Grain Tasks (Macro-tasks)
Data Dependency

1Control flow
Conditional branch
12BPA

BPA

34BPA

BPA

BPA

Block of Psuedo
Assignment Statements

RB

Repetition Block

2753BPA

84RB

6BPA
6RB
BPA

15BPA

765RB

9RB
RB

8BPA
BPA

9BPA

1011
15

7RB

Data dependency
111214END

BPA

12Extended control dependency
Conditional branch

13RBORAND

14RB

Original control flow

BPA
1310

A Macro Flow Graph

A Macro Task
Graph
10

MTG of Su2cor-LOOPS-DO400
Coarse grain parallelism PARA_ALD = 4.3

DOALL

Sequential LOOPSB

BB

11

Data Localization

11326346514

78129101824

11121315

MTG

10511154921

22

2326
dlg3

dlg029

Data Localization Group

273132

PE1121236741481815

5199251129

101316

1720

2226

2130

232427

2820

dlg2

28

8161925dlg1

14713172PE030

3233

MTG after Division
12A schedule fortwo processors

31Inter-loop data dependence analysis in TLG• Define exit-RB in TLG
as Standard-Loop• Find iterations on whicha iteration of Standard-Loop isdata dependent– e.g. Kth of RB3 is data-dep
on K-1th,Kth of RB2,on K-1th,Kth,K+1th of RB1

C RB1(Doall)
DO I=1,101
A(I)=2*I
ENDDO

K-1

C RB2(Doseq)
DO I=1,100
B(I)=B(I-1)+A(I)+A(I+1) K-1
ENDDO
C RB3(Doall)
DO I=2,100
C(I)=B(I)+B(I-1)
ENDDO

Example of TLG
13

K

K+1

K

K

I(RB1)

I(RB2)

I(RB3)

Data-Localization: Loop Aligned Decomposition• Decompose multiple loop (Doall and Seq) into CARs and LRs
considering inter-loop data dependence.
– Most data in LR can be passed through LM.
– LR: Localizable Region, CAR: Commonly Accessed Region
C RB1(Doall)
DO I=1,101
A(I)=2*I
ENDDO
C RB2(Doseq)
DO I=1,100
B(I)=B(I-1)+A(I)+A(I+1)
ENDDO
RB3(Doall)
DO I=2,100
C(I)=B(I)+B(I-1)
ENDDO
C

14

LR

CAR

LR

CAR

DO I=1,33

DO I=34,35

DO I=36,66

DO I=67,68

LR
DO I=69,101

DO I=1,33
DO I=34,34
DO I=35,66
DO I=67,67
DO I=68,100
DO I=2,34

DO I=35,67

DO I=68,100

Decomposition of RBs in TLG• Decompose GCIR into DGCIRp(1≦p≦n)– n: (multiple) num of PCs, DGCIR: Decomposed GCIR
• Generate CAR on which DGCIRp&DGCIRp+1 are data-dep.
• Generate LR on which DGCIRp is data-dep.
RB11
1

RB1<1,2>

RB12

RB1<2,3>
65 66 67 68

33 34 35 36

2 3

RB21

RB2<1,2>

RB22

RB2<2,3>

33 34 35

1 2

RB31
2

DGCIR134 35

RB13
99 100 101

RB23

65 66 67

RB32

99 100RB3366 67

DGCIR2GCIR
15100

DGCIR3

I(RB1)
I(RB2)
I(RB3)

An Example of Data Localization for Spec95 Swim
DO 200 J=1,N
DO 200 I=1,M
UNEW(I+1,J) = UOLD(I+1,J)+
1 TDTS8*(Z(I+1,J+1)+Z(I+1,J))*(CV(I+1,J+1)+CV(I,J+1)+CV(I,J)
2+CV(I+1,J))-TDTSDX*(H(I+1,J)-H(I,J))
VNEW(I,J+1) = VOLD(I,J+1)-TDTS8*(Z(I+1,J+1)+Z(I,J+1))
1*(CU(I+1,J+1)+CU(I,J+1)+CU(I,J)+CU(I+1,J))
2-TDTSDY*(H(I,J+1)-H(I,J))
PNEW(I,J) = POLD(I,J)-TDTSDX*(CU(I+1,J)-CU(I,J))
1-TDTSDY*(CV(I,J+1)-CV(I,J))
200 CONTINUE

DO 210 J=1,N
UNEW(1,J) = UNEW(M+1,J)
VNEW(M+1,J+1) = VNEW(1,J+1)
PNEW(M+1,J) = PNEW(1,J)
210 CONTINUE

DO 300 J=1,N
DO 300 I=1,M
UOLD(I,J) = U(I,J)+ALPHA*(UNEW(I,J)-2.*U(I,J)+UOLD(I,J))
VOLD(I,J) = V(I,J)+ALPHA*(VNEW(I,J)-2.*V(I,J)+VOLD(I,J))
POLD(I,J) = P(I,J)+ALPHA*(PNEW(I,J)-2.*P(I,J)+POLD(I,J))
300 CONTINUE(a) An example of target loop group for data localization
16cache size
01VN
POH

2PN
CU

3UO
CV

4MBUNVO
ZUNVN

PN

UVN
POVPN

PUO

UN
VO

Cache line conflicts occurs
among arrays which share thesame location on cache(b) Image of alignment of arrays oncache accessed by target loops

Data Layout for Removing Line Conflict Misses
by Array Dimension Padding
Declaration part of arrays in spec95 swim
after padding
before padding
PARAMETER (N1=513, N2=513)

PARAMETER (N1=513, N2=544)

COMMON U(N1,N2), V(N1,N2), P(N1,N2),*UNEW(N1,N2), VNEW(N1,N2),
1PNEW(N1,N2), UOLD(N1,N2),*VOLD(N1,N2), POLD(N1,N2),
2
CU(N1,N2), CV(N1,N2),*
Z(N1,N2), H(N1,N2)

COMMON U(N1,N2), V(N1,N2), P(N1,N2),*
UNEW(N1,N2), VNEW(N1,N2),
1
PNEW(N1,N2), UOLD(N1,N2),*
VOLD(N1,N2), POLD(N1,N2),
2
CU(N1,N2), CV(N1,N2),*
Z(N1,N2), H(N1,N2)

4MB

padding
Box: Access range of DLG0174MB

Automatic Parallelization of Still Image Encoding Using JPEG-XR
for the Next Generation Cameras and Drinkable Inner Camera TILEPro64al)
t0X4)

Speed‐ups on TILEPro64 Manycore
0.18[s]

60.00

55.11

50.00

DsSpeed up40.00nal)
rt 1X4)

30.79

30.00

20.00

1コア
10.0[s]10.00

1.00 1.96

15.82
7.86
3.95

0.00

124816

コア数3264

55 times speedup with 64 coresagainst 1 core
Waseda U. & Olympus

18

OSCAR Compile Flow for Simulink Applications
Generate C codeusing Embedded CoderC codeSimulink model

OSCAR Compiler(1) Generate MTG→ Parallelism(2) Generate gantt chart→ Scheduling in a multicore(3) Generate parallelized C codeusing the OSCAR API→ Multiplatform execution(Intel, ARM and SH etc)
19

Speedups of MATLAB/Simulink Image Processing on
Various 4core Multicores(Intel Xeon, ARM Cortex A15 and Renesas SH4A)

Road Tracking, Image Compression : http://www.mathworks.co.jp/jp/help/vision/examples
Buoy Detection : http://www.mathworks.co.jp/matlabcentral/fileexchange/44706‐buoy‐detection‐using‐simulink
Color Edge Detection : http://www.mathworks.co.jp/matlabcentral/fileexchange/28114‐fast‐edges‐of‐a‐color‐image‐‐actual‐color‐‐not‐converting‐to‐grayscale‐/
Vessel Detection : http://www.mathworks.co.jp/matlabcentral/fileexchange/24990‐retinal‐blood‐vessel‐extraction/
20

Parallel Processing of Face Detection
on Manycore, Highend and PC Server
14.00

速度向上率

tilepro64 gcc
SR16k(Power7 8core*4cpu*4node) xlc

12.00

rs440(Intel Xeon 8core*4cpu) icc

速度向上率

10.00

11.55
10.92

9.30

8.00

6.46 6.46
5.74

6.00

4.00

2.00

3.01

3.57 3.67

1.72 1.93 1.93
1.00 1.00 1.00

0.00
12

コア数
4816 OSCAR compiler gives us 11.55 times speedup for 16

cores against 1 core on SR16000 Power7 highend server.
Automatic Parallelization of Face Detection

21Data Localization: Loop Aligned Decomposition• Decomposed loop into LRs and CARs
– LR ( Localizable Region): Data can be passed through LDM– CAR (Commonly Accessed Region): Data transfers are
required among processors

Multi-dimension Decomposition

Single dimension Decomposition

22

Adjustable Blocks
 Handling a suitable block size for eachapplication

 different from a fixed block size in cache each block can be divided into smaller blocks

with integer divisible size to handle small arrays
and scalar variables

23

Multi-dimensional Template Arraysfor Improving Readability• a mapping technique for arrays withvarying dimensions– each block on LDM corresponds tomultiple empty arrays with varyingdimensions– these arrays have an additionaldimension to store the corresponding
block number••••

TA[Block#][] for single dimension
TA[Block#][][] for double dimension
TA[Block#][][][] for triple dimension...

• LDM are represented as a one
dimensional array– without Template Arrays, multidimensional arrays have complex index
calculations

LDM• A[i][j][k] -> TA[offset + i’ * L + j’ * M + k’]– Template Arrays provide readability• A[i][j][k] -> TA[Block#][i’][j’][k’]24Block Replacement Policy Compiler Control Memory blockReplacement

 using live, dead and reuse information of eachvariable from the scheduled result
 different from LRU in cache that does not use
data dependence information

 Block Eviction Priority Policy
1.
2.
3.
4.

(Dead) Variables that will not be accessed laterin the program
Variables that are accessed only by otherprocessor cores
Variables that will be later accessed by thecurrent processor coreVariables that will immediately be accessed by
the current processor core25

Code Compaction by Strip Mining Previous approach produces

duplicate code generates multiple copies of theloop body which leads to code
bloat

 Proposed method adopts code

compaction

 based on strip mining
 multi-dimensional loop can berestructured

CodeDuplication

Strip Mining
26

8 Core RP2 Chip Block Diagram

LCPG0

PCR3
PCR2
PCR1
PCR0

I$
D$
LocalFPU
memory
CPU
16K
16K
I$
D$
I:8K,
D:32K
Local
memory16K
16K
I$Local
D$
CCN
I:8K,
D:32K
memory
User
RAM
64K
16K
16K
BAR
I:8K,
D:32K64K
User
RAM
Local
memoryI:8K,
D:32K64K
User RAM
URAM 64K

Snoop controller 1

Core #3Core#2 FPUCPUCore#1 FPU
CPUI$
D$
Core
#0
CPU
16K FPU16K

Barrier
Sync. Lines

Snoop controller 0

Cluster #0

Cluster #1

Core #7
Core #6
CPU
FPU
Core #5
CPU
FPU
D$I$
Core #4
CPU
16KFPU 16K

D$
I$
CPU
FPU 16K
16K
D$
I$
I:8K,
D:32K
16K
16K
D$ I$
CCN D:32K
UserI:8K,
RAM 16K
64K 16K
BAR
I:8K,
D:32K
User
RAM
64K
Local
memoryUserI:8K,
RAMD:32K
64K
URAM 64K

LCPG1

PCR7
PCR6
PCR5PCR4

On-chip system bus (SuperHyway)

DDR2 SRAM DMA
control control control

LCPG: Local clock pulse generator
PCR: Power Control Register
CCN/BAR:Cache controller/Barrier Register
URAM: User RAM (Distributed Shared Memory)

Speedups by the Proposed Local Memory Management
Compared with Utilizing Shared Memory onBenchmarks Application using RP2

20.12 times speedup for 8cores execution using local memory againstsequential execution using off‐chip shared memory of RP2 for the AACenc28

Conclusions

 This talk introduced automatic cache and local memory

management method using data localization with hierarchical loopaligned decomposition, adjustable block tailored for eachapplication, and block replace considering block reuse distance .
 The local memory management method was implemented on theOSCAR parallelization compiler.
 The performance on the RP2 8 core multicore gave us
 for example,
 20.12 times speedup on 8cores using local memory againstsequential execution using off‐chip shared memory for theAAC encoder though the 8 core execution using sharedmemory gave us 7.14 times speedup.
 11.30 times speedup on 8cores execution using local memory
against sequential execution using off‐chip shared memory for
the SPEC95 swim though the 8 core execution using shared
29
memory gave us 7.40 times speedup.