blob: 51d55e9270ff5b23a03870cdbb30bdf75074d029 [file] [log] [blame]
<!DOCTYPE html>
<html lang="en-US">
<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="/assets/css/custom.css">
<link rel="stylesheet" href="/assets/css/main.css">
<link rel="stylesheet" href="/assets/css/font-awesome.min.css">
<link rel="shortcut icon" href="/favicon.ico?1">
<!-- Begin Jekyll SEO tag v2.8.0 -->
<title>Compiler Design | Nemo</title>
<meta name="generator" content="Jekyll v3.9.2" />
<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="2022-09-10T02:48:41+09:00" />
<meta name="twitter:card" content="summary" />
<meta property="twitter:title" content="Compiler Design" />
<script type="application/ld+json">
{"@context":"https://schema.org","@type":"WebPage","dateModified":"2022-09-10T02:48:41+09:00","datePublished":"2022-09-10T02:48:41+09:00","description":"Overview","headline":"Compiler Design","url":"http://nemo.apache.org//docs/compiler_design/"}</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="/assets/img/nemo-logo.png" alt="Logo"></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/2022/09/10/release-note-0.4/">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="search" 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 class="panel-collapse collapse" id="collapse-1" 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 class="panel-collapse collapse" id="collapse-2" 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 class="panel-collapse" id="collapse-3" 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 class="panel-collapse collapse" id="collapse-4" role="tabpanel" aria-label="Side Navigation">
<div class="list-group">
<a class="list-group-item " href="/docs/contribute/">Contribute</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-5" aria-expanded="false" aria-controls="collapse-5">
Security
</a>
</h4>
</div>
<div class="panel-collapse collapse" id="collapse-5" role="tabpanel" aria-label="Side Navigation">
<div class="list-group">
<a class="list-group-item " href="/docs/security/">Security Guide</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>
<div style="clear:both;">
<p class="text-center">
<br />
<a target="_blank" href="https://github.com/apache/incubator-nemo-website/blob/asf-site/_docs/designs/compiler_design.md" class="btn btn-default" role="button">
<i class="fa fa-pencil fa-lg"></i> Improve this page
</a>
</p>
</div>
<hr>
<ul class="pager">
<li class="previous">
<a href="/docs/passes_and_policies/">
<span aria-hidden="true">&larr;</span> Previous
</a>
</li>
<li class="next">
<a href="/docs/runtime_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 2022 |
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="https://code.jquery.com/jquery-1.12.4.min.js"></script>
<script src="/assets/js/bootstrap.min.js "></script>
<script src="/assets/js/typeahead.bundle.min.js "></script>
<script src="/assets/js/main.js "></script>
</body>
</html>