content/docs/passes_and_policies/index.html - incubator-nemo-website - Git at Google

 <!DOCTYPE html>
 <html>

 <head>
     <meta charset="utf-8">
     <meta http-equiv="X-UA-Compatible" content="IE=edge">
     <meta name="viewport" content="width=device-width, initial-scale=1">

     <link rel="stylesheet" href="/css/main.css">
     <link rel="stylesheet" href="/css/font-awesome.min.css">

     <link rel="shortcut icon" href="/favicon.ico?1">
     <!-- Begin Jekyll SEO tag v2.6.1 -->
 <title>Passes and Policies | Nemo</title>
 <meta name="generator" content="Jekyll v3.4.3" />
 <meta property="og:title" content="Passes and Policies" />
 <meta property="og:locale" content="en_US" />
 <meta name="description" content="Optimization Passes" />
 <meta property="og:description" content="Optimization Passes" />
 <link rel="canonical" href="http://nemo.apache.org//docs/passes_and_policies/" />
 <meta property="og:url" content="http://nemo.apache.org//docs/passes_and_policies/" />
 <meta property="og:site_name" content="Nemo" />
 <meta property="og:type" content="article" />
 <meta property="article:published_time" content="2019-06-28T03:51:21+09:00" />
 <script type="application/ld+json">
 {"url":"http://nemo.apache.org//docs/passes_and_policies/","headline":"Passes and Policies","dateModified":"2019-06-28T03:51:21+09:00","datePublished":"2019-06-28T03:51:21+09:00","description":"Optimization Passes","@type":"WebPage","@context":"https://schema.org"}</script>
 <!-- End Jekyll SEO tag -->


     <link rel="canonical" href="http://nemo.apache.org//docs/passes_and_policies/">
     <link rel="alternate" type="application/rss+xml" title="Nemo" href="http://nemo.apache.org//feed.xml" />
 </head>


 <body>

     <nav class="navbar navbar-default navbar-fixed-top">
     <div class="container navbar-container">
         <div class="navbar-header">
             <button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#navbar" aria-expanded="false" aria-controls="navbar">
         <span class="sr-only">Toggle navigation</span>
         <span class="icon-bar"></span>
         <span class="icon-bar"></span>
         <span class="icon-bar"></span>
       </button>
             <a class="navbar-brand" href="/">
                 <span><img src="/img/nemo-logo.png"></span>
             </a>
         </div>
         <div id="navbar" class="collapse navbar-collapse">
             <ul class="nav navbar-nav">
                 <li  class="active" ><a href="/docs/home/">Docs</a></li>
                 <li ><a href="/apidocs">APIs</a></li>
                 <li ><a href="/pages/downloads">Downloads</a></li>
                 <li ><a href="/pages/talks">Talks</a></li>
                 <li ><a href="/pages/team">Team</a></li>
                 <li ><a href="/pages/license">License</a></li>
                 <li ><a href="/blog/2018/03/23/shuffle-on-nemo/">Blog</a></li>
             </ul>
             <div class="navbar-right">
                 <form class="navbar-form navbar-left">
                     <div class="form-group has-feedback">
                         <input id="search-box" type="text" class="form-control" placeholder="Search...">
                         <i class="fa fa-search form-control-feedback"></i>
                     </div>
                 </form>
                 <ul class="nav navbar-nav">
                     <li><a href="https://github.com/apache/incubator-nemo"><i class="fa fa-github" aria-hidden="true"></i></a></li>
                 </ul>
             </div>
         </div>
     </div>
 </nav>


     <div class="page-content">
         <div class="wrapper">
             <div class="container">
     <div class="row">
         <div class="col-md-4">
           <div class="panel-group" id="accordion" role="tablist" aria-multiselectable="true">

   <div class="panel panel-default">
     <div class="panel-heading">
       <h4 class="panel-title">
         <a role="button" data-toggle="collapse" data-parent="#accordion" href="#collapse-1" aria-expanded="false" aria-controls="collapse-1">
           Getting Started
         </a>
       </h4>
     </div>
     <div id="collapse-1" class="panel-collapse collapse" role="tabpanel" aria-label="Side Navigation">
       <div class="list-group">


           <a class="list-group-item " href="/docs/home/">Overview</a>


           <a class="list-group-item " href="/docs/getting_started/">Getting Started</a>

       </div>
     </div>
   </div>

   <div class="panel panel-default">
     <div class="panel-heading">
       <h4 class="panel-title">
         <a role="button" data-toggle="collapse" data-parent="#accordion" href="#collapse-2" aria-expanded="false" aria-controls="collapse-2">
           Optimizations
         </a>
       </h4>
     </div>
     <div id="collapse-2" class="panel-collapse collapse" role="tabpanel" aria-label="Side Navigation">
       <div class="list-group">


           <a class="list-group-item " href="/docs/ir/">Nemo Intermediate Representation (IR)</a>


           <a class="list-group-item active" href="/docs/passes_and_policies/">Passes and Policies</a>

       </div>
     </div>
   </div>

   <div class="panel panel-default">
     <div class="panel-heading">
       <h4 class="panel-title">
         <a role="button" data-toggle="collapse" data-parent="#accordion" href="#collapse-3" aria-expanded="false" aria-controls="collapse-3">
           System Designs
         </a>
       </h4>
     </div>
     <div id="collapse-3" class="panel-collapse collapse" role="tabpanel" aria-label="Side Navigation">
       <div class="list-group">


           <a class="list-group-item " href="/docs/compiler_design/">Compiler Design</a>


           <a class="list-group-item " href="/docs/runtime_design/">Runtime Design</a>

       </div>
     </div>
   </div>

   <div class="panel panel-default">
     <div class="panel-heading">
       <h4 class="panel-title">
         <a role="button" data-toggle="collapse" data-parent="#accordion" href="#collapse-4" aria-expanded="false" aria-controls="collapse-4">
           Contribute
         </a>
       </h4>
     </div>
     <div id="collapse-4" class="panel-collapse collapse" role="tabpanel" aria-label="Side Navigation">
       <div class="list-group">


           <a class="list-group-item " href="/docs/contribute/">Contribute</a>

       </div>
     </div>
   </div>

 </div>

         </div>

         <div class="col-md-8">
             <h1>Passes and Policies</h1>
             <div id="markdown-content-container"><h3 id="optimization-passes">Optimization Passes</h3>

 <p>The <a href="../ir">Nemo IR</a> can be flexibly modified, both in its logical structure and annotations, through an interface called <em>Nemo optimization pass</em>.
 An <em>optimization pass</em> is basically a function that takes an <em>Nemo IR</em> and outputs an optimized <em>Nemo IR</em>.</p>

 <h5 id="compile-time-passes">Compile-time passes</h5>

 <p>The modification during compile-time can be categorized in different ways:</p>

 <ol>
   <li><strong>Reshaping passes</strong> modify the shape of the IR itself by inserting, regrouping, or deleting IR vertices and edges on an Nemo IR, such as collecting repetitive vertices inside a single loop or inserting metric vertices. This modifies the logical notion of data processing applications.</li>
   <li><strong>Annotating passes</strong> annotate IR vertices and edges with <em>execution properties</em> with the provided logic to adjust and run the workload in the fashion that the user wants.</li>
   <li><strong>Composite passes</strong> are collections of passes that are grouped together for convenience.</li>
 </ol>

 <h5 id="run-time-passes">Run-time passes</h5>

 <p>After the compilation and compile-time optimizations, the <em>Nemo IR</em> gets laid out as a <em>physical execution plan</em> to be submitted to and executed by the <em>Nemo Execution Runtime</em>.
 While execution, an <em>run-time optimization pass</em> can be performed to perform dynamic optimizations, like solving data skew, using runtime statistics.
 It takes the old <em>Nemo IR</em> and metric data of runtime statistics, and sends the newly optimized Nemo IR to execution runtime for the physical plan to be updated accordingly.</p>

 <h3 id="examples">Examples</h3>

 <p>Below are some example optimization passes that are used for different use cases:</p>

 <h4 id="compile-time-passes-1">Compile-time passes</h4>
 <p><strong>Reshaping passes</strong>:</p>
 <ul>
   <li>Common subexpression elimination (CSE): to refactor the commonly occurring operation that unnecessarily computes multiple times.</li>
   <li>Loop invariant code motion (LICM): to extract an operation that does not need to be repetitively done iteratively from a loop.</li>
   <li>Loop Extraction: to observe the DAG structure and extract the repetitive workflow that can be refactored into a loop.</li>
   <li>Data Skew - Metric vertex insertion: to insert a vertex that indicated where to collect metrics and trigger data skew runtime optimization.</li>
 </ul>

 <p><strong>Annotating passes</strong>:</p>
 <ul>
   <li>Parallelism: to determine computational parallelism of each vertices by observing source data size and parallelism information of previous vertices</li>
   <li>Executor placement: to allocate different computations on specific types of resources.</li>
 </ul>

 <h4 id="run-time-passes-1">Run-time passes</h4>
 <ul>
   <li>Data-skew: to evenly re-distribute skewed data into a more evenly-distributed partitions of data.</li>
 </ul>

 <h3 id="optimization-policies">Optimization Policies</h3>

 <p>An <strong>optimization policy</strong> is composed of a specific combination of optimization passes.</p>

 <p>Using a carefully chosen series of <em>optimization passes</em>, we can optimize an application to exploit specific <em>deployement characteristics</em>, by providing appropriate configurations and plan for the execution runtime.
 A complete series of optimization passes is called a <em>policy</em>, which together performs a specific goal.</p>

 <p>For example, to optimize an application to run on evictable transient resources, we can use a specialized executor placement pass, that places computations appropriately on different types of resources,
 and data flow model pass, that determines the fashion in which each computation should fetch its input data, with a number of other passes for further optimization.</p>

 <p>Using different optimization policies for specific goals enables users to flexibly customize and perform data processing for different deployment characteristics.
 This greatly simplifies the work by replacing the work of exploring and rewriting system internals for modifying runtime behaviors with a simple process of using pluggable policies.
 It also makes it possible for the system to promptly meet new requirements through <a href="../extending_Nemo">easy extension of system capabilities</a>.</p>
 </div>
             <p class="text-center">
               <br />
               <a target="_blank" href="https://github.com/apache/incubator-nemo-website/tree/asf-site/_docs/optimization/passes_and_policies.md" class="btn btn-default btn-sm githubEditButton" role="button">
                 <i class="fa fa-pencil"></i> Improve this page
               </a>
             </p>
             <hr>


     <ul class="pager">


         <li class="previous">
           <a href="/docs/ir/">
             <span aria-hidden="true">&larr;</span> Previous
           </a>
         </li>


         <li class="next">
           <a href="/docs/compiler_design/">
             Next <span aria-hidden="true">&rarr;</span>
           </a>
         </li>

       </ul>
     <div class="clear"></div>


         </div>

     </div>
 </div>

         </div>
     </div>

     <footer class="footer">
     <div class="container">

         <p class="text-center">
             Nemo 2019 |
             Powered by <a href="https://github.com/aksakalli/jekyll-doc-theme">Jekyll Doc Theme</a>
         </p>
         <!-- <p class="text-muted">Place sticky footer content here.</p> -->
     </div>
 </footer>

     <script>
   var baseurl = ''
 </script>
 <script src="//code.jquery.com/jquery-1.10.2.min.js"></script>
 <script src="/js/bootstrap.min.js "></script>
 <script src="/js/typeahead.bundle.min.js "></script>

 <script src="/js/main.js "></script>

 </body>

 </html>
	<!DOCTYPE html>
	<html>

	<head>
	<meta charset="utf-8">
	<meta http-equiv="X-UA-Compatible" content="IE=edge">
	<meta name="viewport" content="width=device-width, initial-scale=1">

	<link rel="stylesheet" href="/css/main.css">
	<link rel="stylesheet" href="/css/font-awesome.min.css">

	<link rel="shortcut icon" href="/favicon.ico?1">
	<!-- Begin Jekyll SEO tag v2.6.1 -->
	<title>Passes and Policies \| Nemo</title>
	<meta name="generator" content="Jekyll v3.4.3" />
	<meta property="og:title" content="Passes and Policies" />
	<meta property="og:locale" content="en_US" />
	<meta name="description" content="Optimization Passes" />
	<meta property="og:description" content="Optimization Passes" />
	<link rel="canonical" href="http://nemo.apache.org//docs/passes_and_policies/" />
	<meta property="og:url" content="http://nemo.apache.org//docs/passes_and_policies/" />
	<meta property="og:site_name" content="Nemo" />
	<meta property="og:type" content="article" />
	<meta property="article:published_time" content="2019-06-28T03:51:21+09:00" />
	<script type="application/ld+json">
	{"url":"http://nemo.apache.org//docs/passes_and_policies/","headline":"Passes and Policies","dateModified":"2019-06-28T03:51:21+09:00","datePublished":"2019-06-28T03:51:21+09:00","description":"Optimization Passes","@type":"WebPage","@context":"https://schema.org"}</script>
	<!-- End Jekyll SEO tag -->


	<link rel="canonical" href="http://nemo.apache.org//docs/passes_and_policies/">
	<link rel="alternate" type="application/rss+xml" title="Nemo" href="http://nemo.apache.org//feed.xml" />
	</head>


	<body>

	<nav class="navbar navbar-default navbar-fixed-top">
	<div class="container navbar-container">
	<div class="navbar-header">
	<button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#navbar" aria-expanded="false" aria-controls="navbar">
	<span class="sr-only">Toggle navigation</span>
	<span class="icon-bar"></span>
	<span class="icon-bar"></span>
	<span class="icon-bar"></span>
	</button>
	<a class="navbar-brand" href="/">
	<span><img src="/img/nemo-logo.png"></span>
	</a>
	</div>
	<div id="navbar" class="collapse navbar-collapse">
	<ul class="nav navbar-nav">
	<li class="active" ><a href="/docs/home/">Docs</a></li>
	<li ><a href="/apidocs">APIs</a></li>
	<li ><a href="/pages/downloads">Downloads</a></li>
	<li ><a href="/pages/talks">Talks</a></li>
	<li ><a href="/pages/team">Team</a></li>
	<li ><a href="/pages/license">License</a></li>
	<li ><a href="/blog/2018/03/23/shuffle-on-nemo/">Blog</a></li>
	</ul>
	<div class="navbar-right">
	<form class="navbar-form navbar-left">
	<div class="form-group has-feedback">
	<input id="search-box" type="text" class="form-control" placeholder="Search...">
	<i class="fa fa-search form-control-feedback"></i>
	</div>
	</form>
	<ul class="nav navbar-nav">
	<li><a href="https://github.com/apache/incubator-nemo"><i class="fa fa-github" aria-hidden="true"></i></a></li>
	</ul>
	</div>
	</div>
	</div>
	</nav>


	<div class="page-content">
	<div class="wrapper">
	<div class="container">
	<div class="row">
	<div class="col-md-4">
	<div class="panel-group" id="accordion" role="tablist" aria-multiselectable="true">

	<div class="panel panel-default">
	<div class="panel-heading">
	<h4 class="panel-title">
	<a role="button" data-toggle="collapse" data-parent="#accordion" href="#collapse-1" aria-expanded="false" aria-controls="collapse-1">
	Getting Started
	</a>
	</h4>
	</div>
	<div id="collapse-1" class="panel-collapse collapse" role="tabpanel" aria-label="Side Navigation">
	<div class="list-group">



	<a class="list-group-item " href="/docs/home/">Overview</a>



	<a class="list-group-item " href="/docs/getting_started/">Getting Started</a>

	</div>
	</div>
	</div>

	<div class="panel panel-default">
	<div class="panel-heading">
	<h4 class="panel-title">
	<a role="button" data-toggle="collapse" data-parent="#accordion" href="#collapse-2" aria-expanded="false" aria-controls="collapse-2">
	Optimizations
	</a>
	</h4>
	</div>
	<div id="collapse-2" class="panel-collapse collapse" role="tabpanel" aria-label="Side Navigation">
	<div class="list-group">



	<a class="list-group-item " href="/docs/ir/">Nemo Intermediate Representation (IR)</a>



	<a class="list-group-item active" href="/docs/passes_and_policies/">Passes and Policies</a>

	</div>
	</div>
	</div>

	<div class="panel panel-default">
	<div class="panel-heading">
	<h4 class="panel-title">
	<a role="button" data-toggle="collapse" data-parent="#accordion" href="#collapse-3" aria-expanded="false" aria-controls="collapse-3">
	System Designs
	</a>
	</h4>
	</div>
	<div id="collapse-3" class="panel-collapse collapse" role="tabpanel" aria-label="Side Navigation">
	<div class="list-group">



	<a class="list-group-item " href="/docs/compiler_design/">Compiler Design</a>



	<a class="list-group-item " href="/docs/runtime_design/">Runtime Design</a>

	</div>
	</div>
	</div>

	<div class="panel panel-default">
	<div class="panel-heading">
	<h4 class="panel-title">
	<a role="button" data-toggle="collapse" data-parent="#accordion" href="#collapse-4" aria-expanded="false" aria-controls="collapse-4">
	Contribute
	</a>
	</h4>
	</div>
	<div id="collapse-4" class="panel-collapse collapse" role="tabpanel" aria-label="Side Navigation">
	<div class="list-group">



	<a class="list-group-item " href="/docs/contribute/">Contribute</a>

	</div>
	</div>
	</div>

	</div>

	</div>

	<div class="col-md-8">
	<h1>Passes and Policies</h1>
	<div id="markdown-content-container"><h3 id="optimization-passes">Optimization Passes</h3>

	<p>The <a href="../ir">Nemo IR</a> can be flexibly modified, both in its logical structure and annotations, through an interface called <em>Nemo optimization pass</em>.
	An <em>optimization pass</em> is basically a function that takes an <em>Nemo IR</em> and outputs an optimized <em>Nemo IR</em>.</p>

	<h5 id="compile-time-passes">Compile-time passes</h5>

	<p>The modification during compile-time can be categorized in different ways:</p>

	<ol>
	<li><strong>Reshaping passes</strong> modify the shape of the IR itself by inserting, regrouping, or deleting IR vertices and edges on an Nemo IR, such as collecting repetitive vertices inside a single loop or inserting metric vertices. This modifies the logical notion of data processing applications.</li>
	<li><strong>Annotating passes</strong> annotate IR vertices and edges with <em>execution properties</em> with the provided logic to adjust and run the workload in the fashion that the user wants.</li>
	<li><strong>Composite passes</strong> are collections of passes that are grouped together for convenience.</li>
	</ol>

	<h5 id="run-time-passes">Run-time passes</h5>

	<p>After the compilation and compile-time optimizations, the <em>Nemo IR</em> gets laid out as a <em>physical execution plan</em> to be submitted to and executed by the <em>Nemo Execution Runtime</em>.
	While execution, an <em>run-time optimization pass</em> can be performed to perform dynamic optimizations, like solving data skew, using runtime statistics.
	It takes the old <em>Nemo IR</em> and metric data of runtime statistics, and sends the newly optimized Nemo IR to execution runtime for the physical plan to be updated accordingly.</p>

	<h3 id="examples">Examples</h3>

	<p>Below are some example optimization passes that are used for different use cases:</p>

	<h4 id="compile-time-passes-1">Compile-time passes</h4>
	<p><strong>Reshaping passes</strong>:</p>
	<ul>
	<li>Common subexpression elimination (CSE): to refactor the commonly occurring operation that unnecessarily computes multiple times.</li>
	<li>Loop invariant code motion (LICM): to extract an operation that does not need to be repetitively done iteratively from a loop.</li>
	<li>Loop Extraction: to observe the DAG structure and extract the repetitive workflow that can be refactored into a loop.</li>
	<li>Data Skew - Metric vertex insertion: to insert a vertex that indicated where to collect metrics and trigger data skew runtime optimization.</li>
	</ul>

	<p><strong>Annotating passes</strong>:</p>
	<ul>
	<li>Parallelism: to determine computational parallelism of each vertices by observing source data size and parallelism information of previous vertices</li>
	<li>Executor placement: to allocate different computations on specific types of resources.</li>
	</ul>

	<h4 id="run-time-passes-1">Run-time passes</h4>
	<ul>
	<li>Data-skew: to evenly re-distribute skewed data into a more evenly-distributed partitions of data.</li>
	</ul>

	<h3 id="optimization-policies">Optimization Policies</h3>

	<p>An <strong>optimization policy</strong> is composed of a specific combination of optimization passes.</p>

	<p>Using a carefully chosen series of <em>optimization passes</em>, we can optimize an application to exploit specific <em>deployement characteristics</em>, by providing appropriate configurations and plan for the execution runtime.
	A complete series of optimization passes is called a <em>policy</em>, which together performs a specific goal.</p>

	<p>For example, to optimize an application to run on evictable transient resources, we can use a specialized executor placement pass, that places computations appropriately on different types of resources,
	and data flow model pass, that determines the fashion in which each computation should fetch its input data, with a number of other passes for further optimization.</p>

	<p>Using different optimization policies for specific goals enables users to flexibly customize and perform data processing for different deployment characteristics.
	This greatly simplifies the work by replacing the work of exploring and rewriting system internals for modifying runtime behaviors with a simple process of using pluggable policies.
	It also makes it possible for the system to promptly meet new requirements through <a href="../extending_Nemo">easy extension of system capabilities</a>.</p>
	</div>
	<p class="text-center">
	<br />
	<a target="_blank" href="https://github.com/apache/incubator-nemo-website/tree/asf-site/_docs/optimization/passes_and_policies.md" class="btn btn-default btn-sm githubEditButton" role="button">
	<i class="fa fa-pencil"></i> Improve this page
	</a>
	</p>
	<hr>

















	<ul class="pager">



	<li class="previous">
	<a href="/docs/ir/">
	<span aria-hidden="true">←</span> Previous
	</a>
	</li>





	<li class="next">
	<a href="/docs/compiler_design/">
	Next <span aria-hidden="true">→</span>
	</a>
	</li>

	</ul>
	<div class="clear"></div>


	</div>

	</div>
	</div>

	</div>
	</div>

	<footer class="footer">
	<div class="container">

	<p class="text-center">
	Nemo 2019 \|
	Powered by <a href="https://github.com/aksakalli/jekyll-doc-theme">Jekyll Doc Theme</a>
	</p>
	<!-- <p class="text-muted">Place sticky footer content here.</p> -->
	</div>
	</footer>

	<script>
	var baseurl = ''
	</script>
	<script src="//code.jquery.com/jquery-1.10.2.min.js"></script>
	<script src="/js/bootstrap.min.js "></script>
	<script src="/js/typeahead.bundle.min.js "></script>

	<script src="/js/main.js "></script>

	</body>

	</html>