| <!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>Compiler Design | Nemo</title> |
| <meta name="generator" content="Jekyll v3.4.3" /> |
| <meta property="og:title" content="Compiler Design" /> |
| <meta property="og:locale" content="en_US" /> |
| <meta name="description" content="Overview" /> |
| <meta property="og:description" content="Overview" /> |
| <link rel="canonical" href="http://nemo.apache.org//docs/compiler_design/" /> |
| <meta property="og:url" content="http://nemo.apache.org//docs/compiler_design/" /> |
| <meta property="og:site_name" content="Nemo" /> |
| <meta property="og:type" content="article" /> |
| <meta property="article:published_time" content="2019-12-01T21:11:19+09:00" /> |
| <script type="application/ld+json"> |
| {"url":"http://nemo.apache.org//docs/compiler_design/","headline":"Compiler Design","dateModified":"2019-12-01T21:11:19+09:00","datePublished":"2019-12-01T21:11:19+09:00","description":"Overview","@type":"WebPage","@context":"https://schema.org"}</script> |
| <!-- End Jekyll SEO tag --> |
| |
| |
| <link rel="canonical" href="http://nemo.apache.org//docs/compiler_design/"> |
| <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 " 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 active" 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>Compiler Design</h1> |
| <div id="markdown-content-container"><h3 id="overview">Overview</h3> |
| |
| <p>Compiler takes an arbitrary dataflow program as input, and outputs an optimized physical execution plan to be understood by the execution runtime. The steps are as followings:</p> |
| |
| <ol> |
| <li><strong>Compiler frontend</strong> first translates the logical layer of given dataflow program written in high-level languages, like Apache Beam, into an expressive, general-purpose <a href="../ir">Nemo Intermediate Representation (IR)</a>.</li> |
| <li>Then using the <a href="../passes_and_policies">optimization pass</a> interface provided by the <strong>Compiler optimizer</strong>, the IR can be flexibly reshaped and annotated with a variety of execution properties that configures the underlying runtime behaviors.</li> |
| <li>After being processed by <em>optimization passes</em>, the <strong>Compiler backend</strong> finally lays out the IR into a physical execution plan, composed of tasks and stages, to be carried out by the <a href="../runtime_design">Nemo Execution Runtime</a>.</li> |
| </ol> |
| |
| <h3 id="frontend">Frontend</h3> |
| |
| <p>The frontend of <em>Nemo Compiler</em> translates arbitrary high-level dataflow languages, like Apache Beam, into our expression of <a href="../ir">Nemo IR</a> with an elementary annotation of default <em>execution properties</em>. |
| <strong>Frontend</strong> for different languages are designed as visitors that traverse given applications written in high-level dataflow languages in a topological order. |
| While traversing the logic, it translates each dataflow operators and edges on the way, and appends the translated IR components to the <em>Nemo IR builder</em>. |
| After completing the traversal, the IR builder builds the logical part of the IR after checking its integrity. |
| Integrity check ensures a few factors, such as ensuring vertices without any incoming edges to read source data.</p> |
| |
| <h3 id="optimizer">Optimizer</h3> |
| |
| <p>After the IR is created with its logical structures set up, we need an <a href="../passes_and_policies">Nemo policy</a> to optimize the application for a specific goal. |
| To build Nemo policies safely and correctly, we provide a <em>policy builder</em> interface, which checks for the integrity while registering series of passes in a specific order.</p> |
| |
| <p>For example, if an annotating pass requires information of specific <em>execution properties</em> to perform its work, we specify them as <em>prerequisite execution properties</em>, and check the order and the content of registered passes to ensure that the conditions have been met. |
| We avoid the cases where circular dependencies occur, through the default execution properties that we provide at the initiation of the Nemo IR.</p> |
| |
| <p>Using the policy, the optimizer applies each <em>optimization passes</em> one-by-one in the provided order, and checks for the IR integrity after each optimization has been done, to ensure that the <a href="../ir">IR</a> is not broken.</p> |
| |
| <h3 id="backend">Backend</h3> |
| |
| <p>After the optimizations have been applied, <strong>Compiler backend</strong> finally traverses and lays out the IR into a physical execution plan, which is understood by <a href="../runtime_design">Execution Runtime</a>. |
| In the backend, vertices annotated with the same stage numbers are grouped into stages, to be concurrently run in a distributed fashion, and are expressed in a form of tasks. |
| The generated <em>physical execution plan</em> composed of tasks, task groups (stages), and the data dependency information between them is then submitted to <a href="../runtime_design">Execution Runtime</a> to be scheduled and executed.</p> |
| </div> |
| <p class="text-center"> |
| <br /> |
| <a target="_blank" href="https://github.com/apache/incubator-nemo-website/tree/asf-site/_docs/designs/compiler_design.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/passes_and_policies/"> |
| <span aria-hidden="true">←</span> Previous |
| </a> |
| </li> |
| |
| |
| |
| |
| |
| <li class="next"> |
| <a href="/docs/runtime_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> |