docs/opentimer.html · tom/cpp-taskflow

Fetch the repository succeeded.

richgiteeai

Watch

Unwatch Watching Releases Only Ignoring

1 Star 0 Fork 0

tom/cpp-taskflow

Code Issues 0 Pull Requests 0 Wiki Insights Pipelines

Service

Tencent Cloud Serverless

Create your Gitee Account

Explore and code with more than 14 million developers,Free private repositories !:)

Already have an account? Sign in

文件

master

Branches (1)

Tags (3)

Manage

master

v1.0.2

v1.0.1

v1.0.0

Clone or Download

Clone/Download

HTTPS SSH SVN SVN+SSH Download ZIP

Prompt

To download the code, please copy the following command and execute it in the terminal

To ensure that your submitted code identity is correctly recognized by Gitee, please execute the following command.

git config --global user.name userName 
git config --global user.email userEmail

When using the SSH protocol for the first time to clone or push code, follow the prompts below to complete the SSH configuration.

1 Generate RSA keys.

2 Obtain the content of the RSA public key and configure it in SSH Public Keys

To use SVN on Gitee, please visit the usage guide

When using the HTTPS protocol, the command line will prompt for account and password verification as follows. For security reasons, Gitee recommends configure and use personal access tokens instead of login passwords for cloning, pushing, and other operations.

Username for 'https://gitee.com': userName

Password for 'https://userName@gitee.com': # Private Token

Branches 1

Tags 3

cpp-taskflow

docs

opentimer.html

opentimer.html 10.19 KB

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.14"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Cpp-Taskflow</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link rel="icon" type="image/x-icon" href="favicon.ico" />
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
 $(document).ready(initResizable);
/* @license-end */</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top">
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
 <td id="projectalign" style="padding-left: 0.5em;">
 <div id="projectname"><a href="https://github.com/cpp-taskflow/cpp-taskflow">Cpp-Taskflow</a>
 &#160;<span id="projectnumber">2.4-master-branch</span>
 </div>
 </td>
 </tr>
 </tbody>
</table>
</div>


<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
var searchBox = new SearchBox("searchBox", "search",false,'Search');
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(function() {
 initMenu('',true,false,'search.php','Search');
 $(document).ready(function() { init_search(); });
});
/* @license-end */</script>
<div id="main-nav"></div>
</div>
<div id="side-nav" class="ui-resizable side-nav-resizable">
 <div id="nav-tree">
 <div id="nav-tree-contents">
 <div id="nav-sync" class="sync"></div>
 </div>
 </div>
 <div id="splitbar" style="-moz-user-select:none;" 
 class="ui-resizable-handle">
 </div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(document).ready(function(){initNavTree('opentimer.html','');});
/* @license-end */
</script>
<div id="doc-content">

<div id="MSearchSelectWindow"
 onmouseover="return searchBox.OnSearchSelectShow()"
 onmouseout="return searchBox.OnSearchSelectHide()"
 onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
 name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
 <div class="headertitle">
<div class="title">Static Timing Analysis </div> </div>
</div>
<div class="contents">
<div class="textblock"><p>We have applied Cpp-Taskflow to solve a real-world VLSI static timing analysis problem that incorporates hundreds of millions of tasks and dependencies. The goal is to analyze the timing behavior of a design.</p>
<h1><a class="anchor" id="UseCasesOpenTimer"></a>
OpenTimer: A High-performance Timing Analysis Tool</h1>
<p>Static timing analysis (STA) is an important step in the overall chip design flow. It verifies the static behavior of a circuit design and ensure its correct functionality under the given clock speed. However, efficient parallel timing analysis is extremely challenging to design and implement, due to large irregularity and graph-oriented computing. The following figure shows an extracted timing graph from an industrial design.</p>
<div class="image">
<img src="opentimer_1.png" alt="opentimer_1.png" width="100%"/>
</div>
<p>We consider our research project <a href="https://github.com/OpenTimer/OpenTimer">OpenTimer</a>, an open-source static timing analyzer that has been used in many industrial and academic projects. The first release v1 in 2015 implemented the <em>pipeline-based levelization</em> algorithm using the OpenMP 4.5 task dependency clause. To overcome the performance bottleneck caused by pipeline, we rewrote the core incremental timing engine using Cpp-Taskflow in the second release v2.</p>
<h1><a class="anchor" id="UseCaseOpenTimerProgrammingEffort"></a>
Programming Effort</h1>
<p>The table below measures the software costs of two OpenTimer versions using the Linux tool <a href="https://dwheeler.com/sloccount/">SLOCCount</a>. In OpenTimer v2, a large amount of exhaustive OpenMP dependency clauses that were used to carry out task dependencies are now replaced with only a few lines of flexible Cpp-Taskflow code (9123 vs 4482). The maximum cyclomatic complexity in a single function is reduced from 58 to 20, due to Cpp-Taskflow's programmability.</p>
<div align="center"> <table class="markdownTable">
<tr class="markdownTableHead">
<th class="markdownTableHeadCenter">Tool </th><th class="markdownTableHeadCenter">Task Model </th><th class="markdownTableHeadCenter">Lines of Code </th><th class="markdownTableHeadCenter">Cyclomatic Complexity </th><th class="markdownTableHeadCenter">Cost </th></tr>
<tr class="markdownTableBody" class="markdownTableRowOdd">
<td class="markdownTableBodyCenter">OpenTimer v1 </td><td class="markdownTableBodyCenter">OpenMP 4.5 </td><td class="markdownTableBodyCenter">9123 </td><td class="markdownTableBodyCenter">58 </td><td class="markdownTableBodyCenter">275,287ドル </td></tr>
<tr class="markdownTableBody" class="markdownTableRowEven">
<td class="markdownTableBodyCenter">OpenTimer v2 </td><td class="markdownTableBodyCenter">Cpp-Taskflow </td><td class="markdownTableBodyCenter">4482 </td><td class="markdownTableBodyCenter">20 </td><td class="markdownTableBodyCenter">130,523ドル </td></tr>
</table>
</div><p>OpenTimer v1 relied on a pipeline data structure to adtop loop parallelism with OpenMP. We found it very difficult to go beyond this paradigm because of the insufficient support for dynamic dependencies in OpenMP. With Cpp-Taskflow in place, we can break this bottleneck and easily model both static and dynamic task dependencies at programming time and runtime. The task dependency graph flows computations naturally with the timing graph, providing improved asynchrony and performance. The following figure shows a task graph to carry one iteration of timing update.</p>
<div class="image">
<object type="image/svg+xml" data="opentimer_4.svg" width="100%">opentimer_4.svg</object>
</div>
<h1><a class="anchor" id="UseCaseOpenTimerPerformanceImprovement"></a>
Performance Improvement</h1>
<p>We compare the performance between OpenTimer v1 and v2. We evaluated the runtime versus incremental iterations under 16 CPUs on two industrial circuit designs tv80 (5.3K gates and 5.3K nets) and vga_lcd (139.5K gates and 139.6K nets) with 45nm NanGate cell libraris. Each incremental iteration refers a design modification followed by a timing query to trigger a timing update. In v1, this includes the time to reconstruct the data structure required by OpenMP to alter the task dependencies. In v2, this includes the time to create and launch a new task dependency graph</p>
<div class="image">
<img src="opentimer_2.png" alt="opentimer_2.png" width="70%"/>
</div>
<p>The scalability of Cpp-Taskflow is shown in the Figure below. We used two million-scale designs, netcard (1.4M gates) and leon3mp (1.2M gates) to evaluate the runtime of v1 and v2 across different number of CPUs. There are two important observations. First, v2 is slightly slower than v1 at one CPU (3-4%), where all OpenMP's constructs are literally disabled. This shows the graph overhead of Cpp-Taskflow; yet it is negligible. Second, v2 is consistently faster than v1 regardless of CPU numbers except one. This highlights that Cpp-Taskflow's programming model largely improves the design of a parallel VLSI timing engine that would otherwise not be possible with OpenMP.</p>
<div class="image">
<img src="opentimer_3.png" alt="opentimer_3.png" width="70%"/>
</div>
<h1><a class="anchor" id="UseCaseOpenTimerConclusion"></a>
Conclusion</h1>
<p>Programming models matter. Different models give different implementations. The parallel code sections may run fast, yet the data structures to support a parallel decomposition strategy may outweigh its parallelism benefits. In OpenTimer v1, loop-based OpenMP code is very fast. But it's too costly to maintain the pipeline data structure over iterations.</p>
<h1><a class="anchor" id="UseCaseOpenTimerReferences"></a>
References</h1>
<ul>
<li>T.-W. Huang, C.-X. Lin, G. Guo, and Martin D. F. Wong, &quot;<a href="ipdps19.pdf">Cpp-Taskflow: Fast Task-based Parallel Programming using Modern C++</a>,&quot; <em>IEEE International Parallel and Distributed Processing Symposium (IPDPS)</em>, pp. 974-983, Rio de Janeiro, Brazil, 2019. </li>
<li>Tsung-Wei Huang and Martin Wong, &quot;<a href="huang_15_01.pdf">OpenTimer: A High-Performance Timing Analysis Tool</a>,&quot; <em>IEEE/ACM International Conference on Computer-Aided Design (ICCAD)</em>, pp. 895-902, Austin, TX, 2015. </li>
</ul>
</div></div>
</div>

<div id="nav-path" class="navpath">
 <ul>
 <li class="navelem"><a class="el" href="usecases.html">Real Use Cases</a></li>
 <li class="footer">Generated by
 <a href="http://www.doxygen.org/index.html">
 <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.14 </li>
 </ul>
</div>
</body>
</html>

Copy Edit Raw Blame History

tsung-wei-huang authored 2020年04月26日 04:42 +08:00 . updated otimg

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149

<!-- HTML header for doxygen 1.8.13-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.14"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Cpp-Taskflow</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link rel="icon" type="image/x-icon" href="favicon.ico" />
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
 $(document).ready(initResizable);
/* @license-end */</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
 <td id="projectalign" style="padding-left: 0.5em;">
 <div id="projectname"><a href="https://github.com/cpp-taskflow/cpp-taskflow">Cpp-Taskflow</a>
 &#160;<span id="projectnumber">2.4-master-branch</span>
 </div>
 </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.14 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
var searchBox = new SearchBox("searchBox", "search",false,'Search');
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(function() {
 initMenu('',true,false,'search.php','Search');
 $(document).ready(function() { init_search(); });
});
/* @license-end */</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
 <div id="nav-tree">
 <div id="nav-tree-contents">
 <div id="nav-sync" class="sync"></div>
 </div>
 </div>
 <div id="splitbar" style="-moz-user-select:none;" 
 class="ui-resizable-handle">
 </div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(document).ready(function(){initNavTree('opentimer.html','');});
/* @license-end */
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
 onmouseover="return searchBox.OnSearchSelectShow()"
 onmouseout="return searchBox.OnSearchSelectHide()"
 onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
 name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
 <div class="headertitle">
<div class="title">Static Timing Analysis </div> </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>We have applied Cpp-Taskflow to solve a real-world VLSI static timing analysis problem that incorporates hundreds of millions of tasks and dependencies. The goal is to analyze the timing behavior of a design.</p>
<h1><a class="anchor" id="UseCasesOpenTimer"></a>
OpenTimer: A High-performance Timing Analysis Tool</h1>
<p>Static timing analysis (STA) is an important step in the overall chip design flow. It verifies the static behavior of a circuit design and ensure its correct functionality under the given clock speed. However, efficient parallel timing analysis is extremely challenging to design and implement, due to large irregularity and graph-oriented computing. The following figure shows an extracted timing graph from an industrial design.</p>
<div class="image">
<img src="opentimer_1.png" alt="opentimer_1.png" width="100%"/>
</div>
<p>We consider our research project <a href="https://github.com/OpenTimer/OpenTimer">OpenTimer</a>, an open-source static timing analyzer that has been used in many industrial and academic projects. The first release v1 in 2015 implemented the <em>pipeline-based levelization</em> algorithm using the OpenMP 4.5 task dependency clause. To overcome the performance bottleneck caused by pipeline, we rewrote the core incremental timing engine using Cpp-Taskflow in the second release v2.</p>
<h1><a class="anchor" id="UseCaseOpenTimerProgrammingEffort"></a>
Programming Effort</h1>
<p>The table below measures the software costs of two OpenTimer versions using the Linux tool <a href="https://dwheeler.com/sloccount/">SLOCCount</a>. In OpenTimer v2, a large amount of exhaustive OpenMP dependency clauses that were used to carry out task dependencies are now replaced with only a few lines of flexible Cpp-Taskflow code (9123 vs 4482). The maximum cyclomatic complexity in a single function is reduced from 58 to 20, due to Cpp-Taskflow's programmability.</p>
<div align="center"> <table class="markdownTable">
<tr class="markdownTableHead">
<th class="markdownTableHeadCenter">Tool </th><th class="markdownTableHeadCenter">Task Model </th><th class="markdownTableHeadCenter">Lines of Code </th><th class="markdownTableHeadCenter">Cyclomatic Complexity </th><th class="markdownTableHeadCenter">Cost </th></tr>
<tr class="markdownTableBody" class="markdownTableRowOdd">
<td class="markdownTableBodyCenter">OpenTimer v1 </td><td class="markdownTableBodyCenter">OpenMP 4.5 </td><td class="markdownTableBodyCenter">9123 </td><td class="markdownTableBodyCenter">58 </td><td class="markdownTableBodyCenter">275,287ドル </td></tr>
<tr class="markdownTableBody" class="markdownTableRowEven">
<td class="markdownTableBodyCenter">OpenTimer v2 </td><td class="markdownTableBodyCenter">Cpp-Taskflow </td><td class="markdownTableBodyCenter">4482 </td><td class="markdownTableBodyCenter">20 </td><td class="markdownTableBodyCenter">130,523ドル </td></tr>
</table>
</div><p>OpenTimer v1 relied on a pipeline data structure to adtop loop parallelism with OpenMP. We found it very difficult to go beyond this paradigm because of the insufficient support for dynamic dependencies in OpenMP. With Cpp-Taskflow in place, we can break this bottleneck and easily model both static and dynamic task dependencies at programming time and runtime. The task dependency graph flows computations naturally with the timing graph, providing improved asynchrony and performance. The following figure shows a task graph to carry one iteration of timing update.</p>
<div class="image">
<object type="image/svg+xml" data="opentimer_4.svg" width="100%">opentimer_4.svg</object>
</div>
<h1><a class="anchor" id="UseCaseOpenTimerPerformanceImprovement"></a>
Performance Improvement</h1>
<p>We compare the performance between OpenTimer v1 and v2. We evaluated the runtime versus incremental iterations under 16 CPUs on two industrial circuit designs tv80 (5.3K gates and 5.3K nets) and vga_lcd (139.5K gates and 139.6K nets) with 45nm NanGate cell libraris. Each incremental iteration refers a design modification followed by a timing query to trigger a timing update. In v1, this includes the time to reconstruct the data structure required by OpenMP to alter the task dependencies. In v2, this includes the time to create and launch a new task dependency graph</p>
<div class="image">
<img src="opentimer_2.png" alt="opentimer_2.png" width="70%"/>
</div>
<p>The scalability of Cpp-Taskflow is shown in the Figure below. We used two million-scale designs, netcard (1.4M gates) and leon3mp (1.2M gates) to evaluate the runtime of v1 and v2 across different number of CPUs. There are two important observations. First, v2 is slightly slower than v1 at one CPU (3-4%), where all OpenMP's constructs are literally disabled. This shows the graph overhead of Cpp-Taskflow; yet it is negligible. Second, v2 is consistently faster than v1 regardless of CPU numbers except one. This highlights that Cpp-Taskflow's programming model largely improves the design of a parallel VLSI timing engine that would otherwise not be possible with OpenMP.</p>
<div class="image">
<img src="opentimer_3.png" alt="opentimer_3.png" width="70%"/>
</div>
<h1><a class="anchor" id="UseCaseOpenTimerConclusion"></a>
Conclusion</h1>
<p>Programming models matter. Different models give different implementations. The parallel code sections may run fast, yet the data structures to support a parallel decomposition strategy may outweigh its parallelism benefits. In OpenTimer v1, loop-based OpenMP code is very fast. But it's too costly to maintain the pipeline data structure over iterations.</p>
<h1><a class="anchor" id="UseCaseOpenTimerReferences"></a>
References</h1>
<ul>
<li>T.-W. Huang, C.-X. Lin, G. Guo, and Martin D. F. Wong, &quot;<a href="ipdps19.pdf">Cpp-Taskflow: Fast Task-based Parallel Programming using Modern C++</a>,&quot; <em>IEEE International Parallel and Distributed Processing Symposium (IPDPS)</em>, pp. 974-983, Rio de Janeiro, Brazil, 2019. </li>
<li>Tsung-Wei Huang and Martin Wong, &quot;<a href="huang_15_01.pdf">OpenTimer: A High-Performance Timing Analysis Tool</a>,&quot; <em>IEEE/ACM International Conference on Computer-Aided Design (ICCAD)</em>, pp. 895-902, Austin, TX, 2015. </li>
</ul>
</div></div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
 <ul>
 <li class="navelem"><a class="el" href="usecases.html">Real Use Cases</a></li>
 <li class="footer">Generated by
 <a href="http://www.doxygen.org/index.html">
 <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.14 </li>
 </ul>
</div>
</body>
</html>