Write a Blog >>
PLDI 2021
Sun 20 - Sat 26 June 2021 PLDI
Thu 24 Jun 2021 13:55 - 14:00 at PLDI-A - Talks 4A: Analysis and Synthesis
Fri 25 Jun 2021 01:55 - 02:00 at PLDI-A - Talks 4A: Analysis and Synthesis

Evaluating the complexity of an algorithm is an important step when developing applications, as it impacts both its time and energy performance. Computational complexity, which is the number of dynamic operations regardless of the execution order, is easy to characterize for affine programs. Data movement (or, I/O) complexity is more complex to evaluate as it refers, \emph{when considering all possible valid schedules}, to the minimum required number of I/O between a slow (e.g. main memory) and a fast (e.g. local scratchpad) storage location.

This paper presents IOOpt, a fully automated tool that automatically bounds the data movement of an affine (tilable) program. Given a tilable program described in a DSL, it automatically computes:
1.~a lower bound of the I/O complexity as a symbolic expression of the cache size and program parameters; 2.~an upper bound that allows one to assess the tightness of the lower bound; 3.~a tiling recommendation (loop permutation and tile sizes) that matches the upper bound.
For the lower bound algorithm which can be applied to any affine program, a substantial effort has been made to provide bounds that are as tight as possible for neural networks: In particular, it extends the previous work of Olivry et al. to handle multi-dimensional reductions and expose the constraints associated with small dimensions that are present in convolutions.
For the upper bound algorithm that reasons on the tile band of the program (e.g. output of a polyhedral compiler such as PluTo), the algebraic computations involved have been tuned to behave well on tensor computations such as direct tensor contractions or direct convolutions. As a bonus, the upper bound algorithm that has been extended to multi-level cache can provide the programmer with a useful tiling recommendation.

We demonstrate the effectiveness of our tool by deriving the symbolic lower and upper bounds for several tensor contraction and convolution kernels.
Then we evaluate numerically the tightness of our bound using the convolution layers of Yolo9000 and representative tensor contractions from the TCCG benchmark suite. Finally, we show the pertinence of our I/O complexity model by reporting the running time of the recommended tiled code for the convolution layers of Yolo9000.

Thu 24 Jun

Displayed time zone: Eastern Time (US & Canada) change

13:30 - 14:05
Talks 4A: Analysis and SynthesisPLDI at PLDI-A +12h
13:30
5m
Talk
Phased Synthesis of Divide and Conquer Programs
PLDI
Azadeh Farzan University of Toronto, Victor Nicolet University of Toronto
DOI
13:35
5m
Talk
Synthesizing Data Structure Refinements from Integrity Constraints
PLDI
Shankara Pailoor University of Texas at Austin, Yuepeng Wang University of Pennsylvania, Xinyu Wang University of Michigan, Isil Dillig University of Texas at Austin
DOI
13:40
5m
Talk
Cyclic Program Synthesis
PLDI
Shachar Itzhaky Technion, Hila Peleg Technion, Nadia Polikarpova University of California at San Diego, Reuben N. S. Rowe Royal Holloway University of London, Ilya Sergey Yale-NUS College; National University of Singapore
DOI
13:45
5m
Talk
Adaptive Restarts for Stochastic Synthesis
PLDI
Jason R. Koenig Stanford University, Oded Padon VMWare Research, Alex Aiken Stanford University, USA
DOI
13:50
5m
Talk
JPortal: Precise and Efficient Control-Flow Tracing for JVM Programs with Intel Processor Trace
PLDI
Zhiqiang Zuo Nanjing University, Kai Ji Nanjing University, Yifei Wang Nanjing University, Wei Tao Nanjing University, Linzhang Wang Nanjing University, Xuandong Li Nanjing University, Guoqing Harry Xu University of California at Los Angeles
DOI
13:55
5m
Talk
IOOpt: Automatic Derivation of I/O Complexity Bounds for Affine Programs
PLDI
Auguste Olivry Inria, Guillaume Iooss Inria, Nicolas Tollenaere Inria, Atanas Rountev Ohio State University, Saday Sadayappan University of Utah, Fabrice Rastello Inria
DOI
14:00
5m
Talk
Proving Non-termination by Program Reversal
PLDI
Krishnendu Chatterjee IST Austria, Ehsan Kafshdar Goharshady Ferdowsi University of Mashhad, Petr Novotný Masaryk University, Đorđe Žikelić IST Austria
DOI

Fri 25 Jun

Displayed time zone: Eastern Time (US & Canada) change

01:30 - 02:05
Talks 4A: Analysis and SynthesisPLDI at PLDI-A
01:30
5m
Talk
Phased Synthesis of Divide and Conquer Programs
PLDI
Azadeh Farzan University of Toronto, Victor Nicolet University of Toronto
DOI
01:35
5m
Talk
Synthesizing Data Structure Refinements from Integrity Constraints
PLDI
Shankara Pailoor University of Texas at Austin, Yuepeng Wang University of Pennsylvania, Xinyu Wang University of Michigan, Isil Dillig University of Texas at Austin
DOI
01:40
5m
Talk
Cyclic Program Synthesis
PLDI
Shachar Itzhaky Technion, Hila Peleg Technion, Nadia Polikarpova University of California at San Diego, Reuben N. S. Rowe Royal Holloway University of London, Ilya Sergey Yale-NUS College; National University of Singapore
DOI
01:45
5m
Talk
Adaptive Restarts for Stochastic Synthesis
PLDI
Jason R. Koenig Stanford University, Oded Padon VMWare Research, Alex Aiken Stanford University, USA
DOI
01:50
5m
Talk
JPortal: Precise and Efficient Control-Flow Tracing for JVM Programs with Intel Processor Trace
PLDI
Zhiqiang Zuo Nanjing University, Kai Ji Nanjing University, Yifei Wang Nanjing University, Wei Tao Nanjing University, Linzhang Wang Nanjing University, Xuandong Li Nanjing University, Guoqing Harry Xu University of California at Los Angeles
DOI
01:55
5m
Talk
IOOpt: Automatic Derivation of I/O Complexity Bounds for Affine Programs
PLDI
Auguste Olivry Inria, Guillaume Iooss Inria, Nicolas Tollenaere Inria, Atanas Rountev Ohio State University, Saday Sadayappan University of Utah, Fabrice Rastello Inria
DOI
02:00
5m
Talk
Proving Non-termination by Program Reversal
PLDI
Krishnendu Chatterjee IST Austria, Ehsan Kafshdar Goharshady Ferdowsi University of Mashhad, Petr Novotný Masaryk University, Đorđe Žikelić IST Austria
DOI